POJ 2117 Electricity（割点求连通分量）

题意：
求删除图中任意一个顶点后的最大连通分量数。

思路：

求出每个割点对应的连通分量数，注意这道题目中图可能是不连通的。

这道题目我wa了很多发，主要是我忘了根结点的连通分量数得减1。

为什么呢？因为如果我们用cut[]来记录每个结点对应的连通分量数的话，最后的答案还需要加1。

比如2结点，我们计算所得的cut[2]=3，因为它只计算了它的子树的情况，但是父亲结点并没有计算进去，所以最后需要+1，这个1也就是父亲结点方向也会产生一个连通分量，这是肯定的，因为父亲结点方向就这么一条边。那根结点是没有父亲结点的，所以根结点需要-1。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,ll> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn=10000+5;
 17 
 18 int n, m;
 19 int tot;
 20 int sum;
 21 int ans;
 22 int dfs_clock;
 23 int iscut[maxn];
 24 int pre[maxn];
 25 int head[maxn];
 26 
 27 struct node
 28 {
 29     int v;
 30     int next;
 31 }e[10*maxn];
 32 
 33 void addEdge(int u, int v)
 34 {
 35     e[tot].v=v;
 36     e[tot].next=head[u];
 37     head[u]=tot++;
 38 }
 39 
 40 int dfs(int u, int fa)
 41 {
 42     int lowu=pre[u]=++dfs_clock;
 43     int child=0;
 44     for(int i=head[u];i!=-1;i=e[i].next)
 45     {
 46         int v=e[i].v;
 47         if(!pre[v])
 48         {
 49             child++;
 50             int lowv=dfs(v,u);
 51             lowu=min(lowu,lowv);
 52             if(lowv>=pre[u])   iscut[u]++;
 53         }
 54         else if(pre[v]<pre[u] && v!=fa)
 55         {
 56             lowu=min(lowu,pre[v]);
 57         }
 58     }
 59     if(fa<0 && child>=1)   iscut[u]--;  //这儿很重要，根结点必须-1
 60     return lowu;
 61 }
 62 
 63 void solve()
 64 {
 65     sum=0;
 66     ans=0;
 67     memset(pre,0,sizeof(pre));
 68     memset(iscut,0,sizeof(iscut));
 69     for(int i=0;i<n;i++)
 70     {
 71         if(!pre[i])
 72         {
 73             sum++;
 74             dfs_clock=0;
 75             dfs(i,-1);
 76         }
 77         ans=max(ans,iscut[i]);
 78     }
 79 }
 80 
 81 int main()
 82 {
 83     //freopen("in.txt","r",stdin);
 84     while(~scanf("%d%d",&n,&m))
 85     {
 86         if(n==0 && m==0)  break;
 87         if(m==0)  {printf("%d
",n-1);continue;}
 88         tot=0;
 89         memset(head,-1,sizeof(head));
 90         while(m--)
 91         {
 92             int u,v;
 93             scanf("%d%d",&u,&v);
 94             addEdge(u,v);
 95             addEdge(v,u);
 96         }
 97         solve();
 98         printf("%d
",sum+ans);
 99     }
100     return 0;
101 }