1 /* 2    题意：给定一个连通的无向图G，至少要添加几条边，才能使其变为强连通图（指的是边强联通）。  3    思路：利用tarjan算法找出所有的双联通分量！然后根据low[]值的不同将双联通分量 4    进行缩点，最后图形会变成一棵树！也就是添加至少多少条边使一棵树变成强联通图！  5    

 6    知识点：若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么 7            至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2  8             9 */10 #include<iostream>11 #include<cstring>12 #include<cstdio>13 #include<algorithm>14 #include<vector>15 #define N 100516 using namespace std;17 vector<int>g[N]; 18 int low[N], pre[N]; 19 int deg[N];20 int n, m;21 int cnt;22 int dfsClock;23 void dfs(int u, int fa){24     low[u]=pre[u]=++dfsClock;25     int len=g[u].size();26     for(int i=0; i<len; ++i){27         int v=g[u][i];28         if(!pre[v]){29            dfs(v, u);30            low[u]=min(low[u], low[v]);31         }32         else if(pre[v] < pre[u] && fa!=v)33            low[u]=min(pre[v], low[u]);34     }35 }36 37 int main(){38     while(scanf("%d%d", &n, &m)!=EOF){39         memset(pre, 0, sizeof(pre));40         memset(deg, 0, sizeof(deg));41         while(m--){42            int u, v;43            scanf("%d%d", &u, &v);44            g[u].push_back(v);45            g[v].push_back(u);46         }47         cnt=0;48         dfsClock=0;49         dfs(1, -1);50         for(int i=1; i<=n; ++i){51            int len=g[i].size();52            for(int j=0; j<len; ++j){53                   int v=g[i][j];54                   if(low[i]!=low[v])55                    ++deg[low[i]];56            }57         }58         for(int i=1; i<=n; ++i)59             if(deg[i]==1)60                ++cnt;61         printf("%d\n", (cnt+1)/2);62         for(int i=1; i<=n; ++i)63            g[i].clear();64     }65     return 0;66 }