POJ3352Road Construction（无向图强连通）

无向图强连通分量缩点知道一个等式：

若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么

至少增加的边数 =（这棵树总度数为1的结点数 + 1 ）/ 2

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stack>
 5 #include<algorithm>
 6 #include<stdlib.h>
 7 using namespace std;
 8 #define N 1010
 9 #define M 2010
10 struct node
11 {
12     int u,v,next;
13 }edge[M];
14 stack<int>s;
15 int head[N],pre[N],low[N],sccno[N],scc,dep,t,de[N],vis[N],w[N][N];
16 void init()
17 {
18     t = 0;
19     memset(head,-1,sizeof(head));
20     scc=0;dep=0;
21     memset(sccno,0,sizeof(sccno));
22     memset(low,0,sizeof(low));
23     memset(pre,0,sizeof(pre));
24     memset(vis,0,sizeof(vis));
25 }
26 void add(int u,int v)
27 {
28     edge[t].u = u;
29     edge[t].v = v;
30     edge[t].next = head[u];
31     head[u] = t++;
32 }
33 void dfs(int u,int fa)
34 {
35     low[u] = pre[u] = ++dep;
36     s.push(u);
37     for(int i = head[u] ; i!=-1 ; i = edge[i].next)
38     {
39         int v = edge[i].v;
40         if(v==fa) continue;
41         if(!pre[v])
42         {
43             dfs(v,u);
44             low[u] = min(low[u],low[v]);
45         }
46         else if(!sccno[v])
47         low[u] = min(low[u],pre[v]);
48     }
49     if(low[u]==pre[u])
50     {
51         scc++;
52         for(;;)
53         {
54             int x = s.top();s.pop();
55             sccno[x] = scc;
56             if(x==u) break;
57         }
58     }
59 }
60 int main()
61 {
62     int i,n,m,kk=0;
63     char str[100];
64     while(cin>>n>>m)
65     {
66         kk++;init();
67         memset(w,0,sizeof(w));
68         memset(de,0,sizeof(de));
69         int a,b;
70         while(m--)
71         {
72             scanf("%d%d",&a,&b);
73             add(a,b);add(b,a);
74         }
75         dfs(1,1);
76         for(i = 0 ; i < t  ; i++)
77         {
78             int u = edge[i].u,v = edge[i].v;
79             if(!w[u][v]&&sccno[u]!=sccno[v])
80             {
81                 w[u][v]  = w[v][u]= 1;
82                 de[sccno[u]]++;
83                 de[sccno[v]]++;
84             }
85         }
86         int num=0;
87         for(i = 1; i <= scc ; i++)
88         if(de[i]==1) num++;
89         cout<<(num+1)/2<<endl;
90     }
91     return 0;
92 }

View Code