题意：
给你一个无向图，你需要找出来其中有几个桥
桥：
1、存在重边必定不为桥
2、low[v]>dfn[u]
代码：
//题意很清晰 //就是这个需要先找出来原无向图中的桥个数，然后在判断添加边之后会不会形成环，形成环的话，这个环里面的是没有桥的 #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<map> #include<math.h> #include<set> #include<queue> using namespace std; typedef long long ll; const int maxn=100005; const int mod=26; const int INF=0x3f3f3f3f; const int block=300; int dfn[maxn],low[maxn],isbridge[maxn],visit[maxn],depth; int pre[maxn],bridge_cnt; vector<int>w[maxn]; void dfs(int u,int fu) //这是无向图找桥的方法，当无环图出现环的时候，那么这个里面没有桥，其他情况有 { //有向图找桥的时候，当出现一个环的时候这个环里面的边也都不是桥，相当于把这个环缩成了一个超级点 dfn[u]=low[u]=++depth; visit[u]=1; int flag=1; int len=w[u].size(); for(int i=0;i<len;++i) { int v=w[u][i]; //printf("%d %d**1** ",u,v); if(flag && v==fu) { //printf("%d %d**2** ",u,v); flag=0; continue; } if(dfn[v]==-1) { //printf("%d %d**3** ",u,v); pre[v]=u; dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) { //printf("%d %d**666** ",u,v); isbridge[v]=1; bridge_cnt++; } } else if(visit[v]) //printf("%d %d**4** ",u,v), low[u]=min(dfn[v],low[u]); } //无环图找桥是不需要dfn[u]==low[u]这个判断的，具体为什么可以自己写一下 } int lca(int u,int v) //找到公共最近父节点 { int res=0; if(dfn[u]<dfn[v]) swap(u,v); while(dfn[u]>dfn[v]) { if(isbridge[u]) { isbridge[u]=0; res++; } u=pre[u]; //pre是u父亲节点 } while(dfn[v]>dfn[u]) { if(isbridge[v]) { isbridge[v]=0; res++; } v=pre[v]; } //经过上面两个while，这样dfn[u]==dfn[v]此时他们就到达了最近公共父节点 return res; } int main() { int n,m,t=0; while(~scanf("%d%d",&n,&m) && (n || m)) { for(int i=1;i<=n;++i) { w[i].clear(); } int u,v; while(m--) { scanf("%d%d",&u,&v); w[u].push_back(v); w[v].push_back(u); } memset(dfn,-1,sizeof(dfn)); memset(isbridge,0,sizeof(isbridge)); memset(visit,0,sizeof(visit)); depth=bridge_cnt=0; for(int i=1;i<=n;++i) //输入的原图就是所有点都连接在一起，不会出现好几个连通图 if(dfn[i]==-1) dfs(1,-1); //printf("%d** ",bridge_cnt); int q; scanf("%d",&q); printf("Case %d: ", ++t); while(q--) { scanf("%d%d",&u,&v); int ans=lca(u,v); bridge_cnt-=ans; printf("%d ",bridge_cnt); } //printf(" "); } return 0; }