这个题目网上有很多答案，代码也很像，不排除我的。大家的思路应该都是taijan求出割边，然后找两个点的LCA（最近公共祖先），这两个点和LCA以及其他点构成了一个环，我们判断这个环上的割边有几条，我们的答案就少几个。
有人问，这个题重边怎么办呢，重边肯定不是桥啊。额……对于这个我只能说，这个题的原始图应该是没有重边的，后来加的边可能会有重边，不过不影响我们的判断，因为我们通过标记点的方式去判的。（这个题还是应该说明一下啊，题目有点问题……）。
其次，这个题的好玩之处来了，网上人分享的代码，居然过不了一组很简单的样例（如下），（现在大多人可能已经修正了），其实这个原因我应该是找到了，那就是dfn（出生日期）和deep（深搜的层数）的使用错误，当你使用deep的时候交换两者的值是没错的，因为我们总能让他们调整到一层上，然后他们的LCA也一定在一层上了，使用fa数组可以追溯到他们的LCA。然而如果是用dfn交换两者的值就是错误的了，因为即使你调整了他们的值满足一定的大小关系，他们也不一定在一层上，很有可能追溯到了环的外面，所以在追溯的时候很可能会多减上几条边。也就是出现了下面的样例，答案是1，有人输出了0；
其实这个地方我一直有一个疑惑，那就是使用dfn判断的时候，最后的时候居然会出现二者不相等的情况，这与深搜的性质相违背，到现在也没找到一个样例可以说明他是正确的，我确实感觉到当判断完前两个循环的时候dfn【u】就是他们的LCA了，这个疑惑我先放到这里，便于以后解答，在以后我会主要选择记录深度的方法去做，比较好理解，比较保险（就如我下面代码里的方法）
附：这个题还有一个解决方法，就是求双连通分量，通过判断两点是否在一个分量里判断两点之间的边是否为桥，然后再合并这两个点。求连通分量的办法一种是并查集，在判断的时候合并到一个集合里，一种是栈的储存方式，id数组，与有向图求强连通分量的方法一致。注意无向图的双连通分量不是指能否相互到达，而是指这个分量里面不含桥，所以当两个点不在一个集合中的时候，这条边一定就是桥。
6 5
1 2
2 3
2 4
3 5
4 6
1
5 6
答案：1
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 100010 int head[maxn],dfn[maxn],low[maxn],fa[maxn],deep[maxn]; int all,tot,bridge[maxn],brinum; struct Edge { int to,nxt; } edge[4*maxn]; void addadge(int a,int b) { edge[tot].to = b; edge[tot].nxt = head[a]; head[a] = tot++; } void dfs(int u,int pa) { low[u] = dfn[u] = ++all; deep[u] = deep[pa] + 1; for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(!dfn[v]) { fa[v] = u; dfs(v,u); low[u] = min(low[u],low[v]); if(low[v] > dfn[u]) { bridge[v] = 1; brinum++; } } else if(v != pa) low[u] = min(low[u],dfn[v]); } } void lca(int a,int b) { while(deep[a] > deep[b]) { if(bridge[a]) { bridge[a] = 0; brinum--; } a = fa[a]; } while(deep[b] > deep[a]) { if(bridge[b]) { bridge[b] = 0; brinum--; } b = fa[b]; } while(a != b) { if(bridge[a]) { bridge[a] = 0; brinum--; } if(bridge[b]) { bridge[b] = 0; brinum--; } a = fa[a]; b = fa[b]; } } int main() { int n,m,q,a,b,ca = 0; while(~scanf("%d%d",&n,&m)) { if(!n && !m) break; for(int i = 0; i <= n; i++) { head[i] = -1; dfn[i] = 0; low[i] = 0; fa[i] = i; deep[i] = 0; bridge[i] = 0; } tot = 0; all = 0; brinum = 0; for(int i = 0; i < m; i++) { scanf("%d%d",&a,&b); addadge(a,b); addadge(b,a); } dfs(1,1); scanf("%d",&q); printf("Case %d: ",++ca); while(q--) { scanf("%d%d",&a,&b); lca(a,b); printf("%d ",brinum); } puts(""); } return 0; }