首页 > 代码库 > HDU 4587 无向图的割点

HDU 4587 无向图的割点

2024-07-22 08:19:05   230人阅读

TWO NODES

Time Limit: 24000/12000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1137    Accepted Submission(s): 333


Problem Description
Suppose that G is an undirected graph, and the value of stab is defined as follows:

Among the expression,G-i, -j is the remainder after removing node i, node j and all edges that are directly relevant to the previous two nodes. cntCompent is the number of connected components of X independently.
Thus, given a certain undirected graph G, you are supposed to calculating the value of stab.
 

 

Input
The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).
Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.
 

 

Output
For each graph in the input, you should output the value of stab.
 

 

Sample Input
4 5
0 1
1 2
2 3
3 0
0 2
 

 

Sample Output
2
 
题目意思：
一个无向图，有n个结点m条边，求删除两个结点剩下图中连通分量最多为多少个。
 
思路：
该题限制时间为12MS，不用多想了，暴力吧。。枚举删除的第一个结点，然后求出剩下图中割点及其儿子个数（即为删除该割点后多出的连通分量数），不断更新最大值。思路很简单，代码细节很多，wa了很多次。。。
 
代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8  9 #define N 500510 11 vector<int>ve[N];12 int dfn[N], low[N], visited[N];13 int gd[N];14 int n, m, dfn_clock, lt_num, root, son, del;15 16 void tarjan(int u,int fa){17     if(u==del) return;           //删除第一个点 18     int i, j, k;19     dfn[u]=low[u]=dfn_clock++;20     visited[u]=1;21     for(i=0;i<ve[u].size();i++){22         int v=ve[u][i];23         if(v==del) continue;         //删除第一个点 24         if(v==fa) continue;25         if(!visited[v]){26             tarjan(v,u);27             low[u]=min(low[u],low[v]);28             if(u==root) son++;29             else if(low[v]>=dfn[u]) gd[u]++;   //对应割点儿子数目+1 30         }31         else low[u]=min(low[u],dfn[v]);32     }33 }34 35 main()36 {37      int i, j, k, x, y;38      while(scanf("%d %d",&n,&m)==2){39          for(i=0;i<=n;i++) ve[i].clear();40          while(m--){41              scanf("%d %d",&x,&y);42              ve[x].push_back(y);43              ve[y].push_back(x);44          }45          int ans=-1;46          for(i=0;i<n;i++){         //枚举第一个删除的点 47              memset(visited,0,sizeof(visited));48              memset(dfn,0,sizeof(dfn));49              memset(gd,0,sizeof(gd));50              visited[i]=1;51              dfn_clock=lt_num=son=0;52              del=i;53              int maxson=0;54              55              for(j=0;j<n;j++){     //从剩下图中找删除的另一个点，另一个点必是割点 56                  if(!visited[j]){57                      lt_num++;58                  //    visited[j]=1;59                      root=j;60                      tarjan(j,-1);61                      maxson=max(maxson,son);62                      son=0;63                  }64              }65              if(lt_num==n-1) lt_num--;      //在这wa了很多次，试试这个数据：5 0 66              for(j=0;j<n;j++) ans=max(ans,gd[j]+lt_num);67              ans=max(ans,maxson+lt_num-1);68          }69          printf("%d\n",ans);70      }71 }

 

 

HDU 4587 无向图的割点


联系
我们