题目链接：
ZOJ2588
题意：
给出一个无向的连通图,问去掉图中的哪些边,都会使图将不连通
题解思路：
割边的求解：
1、需要用到Tarjan算法的框架，首先求出dfn low 两个数组
当递归返回时 判断dfn[u]和low[v]的关系
只有当dfn[u] < low[v] 的情况下u-v是一条割边(u是关节点 ，，且u-v不含重边，即dfn[u] ！= low[v])
2、题目中还有出现重边的情况 重边是不可能成为割边的 我们需要对重边进行标记
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define maxn 10050using namespace std;struct node{int to,tag,id;};vector<node>edge[maxn];int dfn[maxn],low[maxn];int num,n,ans;int vis[maxn*10];void init(){memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));num=1;ans=0;for(int i=1; i<=n; i++)edge[i].clear();}void addedge(int a,int b,int x){int flag=0,i;for(i=0; i<edge[a].size(); i++)if(edge[a][i].to==b)//判重边 有重边的边不可能是割边{edge[a][i].tag=1;//标记flag=1;break;}if(flag)//反向边的标号也是iedge[b][i].tag=1;else{edge[a].push_back( {b,0,x});edge[b].push_back( {a,0,x});}}void Tarjan(int u,int pre){dfn[u]=low[u]=num++;for(int i=0; i<edge[u].size(); i++){int v=edge[u][i].to;if(!dfn[v]){Tarjan(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]&&edge[u][i].tag==0){vis[edge[u][i].id]=1;//id号边是割边ans++;}}else if(pre!=v)//保证不是前一条边的反向边low[u]=min(low[u],dfn[v]);}}int main(){// freopen("out.txt","w",stdout);int T,m,a,b;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);init();for(int i=1; i<=m; i++){scanf("%d%d",&a,&b);addedge(a,b,i);}Tarjan(1,-1);//for(int i=1;i<=n;i++)//cout<<dfn[i]<<" "<<low[i]<<endl;cout<<ans<<endl;int flag=0;for(int i=1;i<=m;i++)if(vis[i])if(!flag){flag=1;cout<<i;}elsecout<<" "<<i;if(ans)//PE多发 注意当ans=0时 要少一个回车cout<<endl;if(T)cout<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
没有创造的生活不能算生活，只能算活着。
