题目分析：就是求无向图的桥。
tarjan算法跑一遍，和无向图割点十分类似，这里要找low[v] > dfn[u]的边(u,v)便是割边，因为v是u的孩子，但是v无法访问到u的祖先，那么断开这条边原图必不连通，因此这是桥。这题会有平行边，平行边必定不是桥。所以dfs的时候要判断一下。
详情请见代码：
#include#include #include #include using namespace std; const int N = 10005; const int M = 500005; int m,n,num,ansnum,dfns; int head[N],ans[M],low[N],dfn[N]; bool vis[N]; struct node { int to,next,id; }bridge[M<<1]; void build(int s,int e,int id) { bridge[num].id = id; bridge[num].to = e; bridge[num].next = head[s]; head[s] = num ++; } void dfs(int cur,int fa) { vis[cur] = true; int chongbian = 0; dfn[cur] = low[cur] = dfns ++; for(int i = head[cur];i != -1;i = bridge[i].next) { if(fa == bridge[i].to) chongbian ++; if(vis[bridge[i].to] == false) { dfs(bridge[i].to,cur); low[cur] = min(low[cur],low[bridge[i].to]); if(low[bridge[i].to] > dfn[cur]) ans[ansnum ++] = bridge[i].id; } else if(fa != bridge[i].to || chongbian > 1) low[cur] = min(low[cur],dfn[bridge[i].to]); } } void tarjan() { int i; dfns = 1; memset(vis,false,sizeof(vis)); memset(dfn,0,sizeof(dfn)); for(i = 1;i <= n;i ++) if(vis[i] == false) dfs(i,-1); printf("%d\n",ansnum); sort(ans,ans + ansnum); for(i = 0;i < ansnum;i ++) printf(i == ansnum - 1 "%d\n":"%d ",ans[i]); } int main() { int t,i; int a,b; scanf("%d",&t); while(t --) { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); num = ansnum = 0; for(i = 1;i <= m;i ++) { scanf("%d%d",&a,&b); build(a,b,i); build(b,a,i); } tarjan(); if(t) puts(""); } return 0; }