题意:有一些联通的地方，如果2点间只有一条路径，这样的边叫做桥，现在让你添加一个桥，使最后的桥最少，问最少的桥使多少？
先求一次强连通分量，然后图就分成了几个块，将这几个块看做点，求出总共有多少条重建图中的边，然后再求出最长的边，这样答案就是总共
边数 - 最长的边的长度。原来的标记手法过了几题，但是做这题有点问题，用了另一个手法。
#pragma comment(linker, "/STACK:102400000,102400000") #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 1000000001 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 200010; struct node { int to; int next; int vis; }edge[1000010 * 2],a[1000010 * 2]; struct fnode { int x; int val; }; int n,m,ind,pre[MAXN],ins[MAXN],low[MAXN],dfn[MAXN],vis[MAXN],num[MAXN],fpre[MAXN]; int fp,len,p; stack<int>s; void Init() { fp = 1; ind = 0; while(!s.empty())s.pop(); memset(num,0,sizeof(num)); memset(ins,0,sizeof(ins)); memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); } void add(int x,int y) { edge[ind].to = y; edge[ind].vis = 0; edge[ind].next = pre[x]; pre[x] = ind ++; } void dfs(int rt,int k,int fa) { s.push(rt); vis[rt] = ins[rt] = 1; low[rt] = dfn[rt] = k; for(int i = pre[rt]; i != -1; i = edge[i].next){ int t = edge[i].to; if(edge[i].vis)continue; edge[i].vis = edge[i^1].vis = 1; //原来判断 fa != t 但是有重边的情况这种标记不行。 if(!dfn[t]){ dfs(t,k+1,rt); low[rt] = min(low[rt],low[t]); } else{ low[rt] = min(dfn[t],low[rt]); } } if(low[rt] == dfn[rt]){ while(!s.empty()){ int temp = s.top(); s.pop(); num[temp] = fp; if(temp == rt)break; } fp ++; } } void add_b(int x,int y) { a[ind].to = y; a[ind].next = fpre[x]; fpre[x] = ind ++; } void build(int rt) { vis[rt] = 1; for(int i = pre[rt]; i != -1; i=edge[i].next){ int t = edge[i].to; if(!vis[t]){ if(num[t] != num[rt]){ add_b(num[t],num[rt]); add_b(num[rt],num[t]); } build(t); } } } void bfs(int rt) { queue<fnode>q; fnode temp; temp.val = 0; temp.x = rt; vis[rt] = 1; q.push(temp); while(!q.empty()){ temp = q.front(); q.pop(); for(int i = fpre[temp.x]; i != -1; i = a[i].next){ int t = a[i].to; if(!vis[t]){ fnode ft; ft.val = temp.val + 1; ft.x = t; vis[t] = 1; q.push(ft); if(ft.val > len){ len = ft.val; p = ft.x; } } } } } int main() { while(~scanf("%d%d",&n,&m)){ if(!n && !m)break; Init(); for(int i = 1; i <= m; i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i = 1; i <= n; i++){ if(!dfn[i]){ dfs(i,1,-1); } } memset(vis,0,sizeof(vis)); ind = 1; memset(fpre,-1,sizeof(fpre)); for(int i = 1; i <= n; i++){ if(!vis[i]){ build(i); } } len = 0; p = 1; memset(vis,0,sizeof(vis)); bfs(1); len = 0; memset(vis,0,sizeof(vis)); bfs(p); fp -= 1; int ans = fp - 1 - len; //cout<<"fp = "<<fp<<" len = "<<len<<endl; cout<<(ans > 0 ? ans : 0)<<endl; } return 0; }