題意：N個島有M個橋相連，燒掉盡可能多的橋，讓N個島仍然相連，問必須不能燒掉的橋的個數(shù)及編號。就是求割邊

割邊與割點差不多都是tarjan式的dfs，有兩個地方不一樣 見代碼

代碼：?

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #define nMAX 10005 #define mMAX 200010 #define Min(a,b)a<b?a:b using namespace std; int head[nMAX],dfn[nMAX],low[nMAX],bridge[mMAX]; int n,times,s_edge,nbridge; struct Edge {int v,nxt,id;//id記錄第幾個橋 }edge[mMAX];void addedge(int u,int v,int id) {edge[++s_edge].v=v;edge[s_edge].nxt=head[u];edge[s_edge].id=id;head[u]=s_edge;edge[++s_edge].v=u;edge[s_edge].nxt=head[v];edge[s_edge].id=id;head[v]=s_edge;} void tarjan(int u,int fa) {bool fg=0;//判斷重邊,重邊不是割邊,炸掉不被dfn[u]=low[u]=++times;for(int e=head[u];e;e=edge[e].nxt){int v=edge[e].v;if(v==fa&&!fg)//判斷重邊{fg=1;continue;}if(!dfn[v]){tarjan(v,u);low[u]=Min(low[u],low[v]);//1.沒有根節(jié)點的判斷 2.割點中if(low[v]>=dfn[u])，//而割邊if(low[v]>dfn[u)沒有=號if(low[v]>dfn[u])bridge[nbridge++]=edge[e].id;}else low[u]=Min(low[u],dfn[v]);} } void init() {memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));s_edge=1;times=0; } int main() {int CASE,i,j,k,m;scanf("%d",&CASE);while(CASE--){init();scanf("%d%d",&n,&m);for(k=1;k<=m;k++){scanf("%d%d",&i,&j);addedge(i,j,k);}nbridge=0;tarjan(1,-1);printf("%d\n",nbridge);if(nbridge){sort(bridge,bridge+nbridge);for(i=0;i<nbridge-1;i++)printf("%d ",bridge[i]);printf("%d\n",bridge[i]);}if(CASE)printf("\n");}return 0; }

　　

　　

轉(zhuǎn)載于:https://www.cnblogs.com/sdau10kuaile/archive/2012/04/10/2441349.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ 2588 Burning Bridges 割边的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。