爱华网题意：一个连通的无向图，求至少需要添加几条边，救能保证删除任意一条边，图仍然是连通的。
思路：边的双连通图。其实就是要求至少添加几条边，可以使整个图成为一个边双连通图。用tarjan算法(求割点割边)求出low数组，这里可以简化，然后依据“low相同的点在一个边连通分量中”，缩点之后构造成树(这里可以直接利用low[]数组，low[i]即为第i节点所在的连通分量的标号)。求出树中出度为1的节点数left，答案即为(leaf+1)/2。
源代码：(348K，79MS)
#include<iostream>
#include<vector>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int Max = 1005;
int n, m, rt, cnt;
int vis[Max], dfn[Max], low[Max];
vector<int> adj[Max];
void dfs(int u, intfa){// 简化了的tarjan。
vis[u] =1;
dfn[u] =low[u] = cnt ++;
for(int i =0; i < adj[u].size(); i ++){
int v = adj[u][i];
if(vis[v] == 1 && v != fa)
low[u] = min(low[u], dfn[v]);
if(vis[v] == 0){
dfs(v, u);
low[u] = min(low[u], low[v]);
}
}
vis[u] =2;
}
int main(){
int u, v,i;
while(cin>> n >>m){
memset(vis, 0, sizeof(vis));
for(i = 1; i <= n; i ++)
adj[i].clear();
while(m --){
cin >> u>> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
rt = 1, cnt = 0;
dfs(1, rt);
int d[Max], leaf = 0;
memset(d, 0, sizeof(d));
for(u = 1; u <= n; u ++)
for(i = 0; i < adj[u].size(); i ++)
if(low[u] != low[adj[u][i]])
d[low[u]] ++;// 表示第low[u]个连通分量的度数+1。
for(i = 0; i <= n; i ++)
if(d[i] == 1) leaf ++;
cout << (leaf+1)/2<< endl;
}
return0;
}
