所謂0->n-1路徑上一定要經(jīng)過的割邊，就是0->n-1任意一條路徑上的割邊，因?yàn)楦钸吺潜亟?jīng)之路。其實(shí)這題跟ZOJ 2588是同一個(gè)題，稍微變化就可以得到答案了，不過這題我當(dāng)時(shí)的模板貌似寫挫了，對(duì)邊進(jìn)行判重的時(shí)候進(jìn)行了暴力，其實(shí)可以用set存一下，那么查找的復(fù)雜度可以降到log(n).
具體求割邊的方法可以看這個(gè)：
http://www.shnenglu.com/abilitytao/archive/2009/09/26/97267.html不過程序貌似有問題，代碼寫得比較挫，就不值得借鑒了。
#include<iostream>
#include<algorithm>
#include<set>
#include<cstdio>
#include<memory.h>
using namespace std;
#define min(a,b) ((a<b?a:b))
set<int>mm;//存儲(chǔ)重邊
int const maxn=10010;//頂點(diǎn)數(shù)
int const maxm=100010;//邊數(shù)
int n,m;
struct Edge
{
int u,v,idx;
bool operator<(Edge o)const
{
if(u!=o.u)
return u<o.u;
else
return v<o.v;
}
}e[maxm*2];
struct node
{
int t;
int idx;
node *next;
}edge[maxm*2];
node *adj[maxn];
int len=0;
void addedge(int u,int v,int idx)//加入一條邊
{
edge[len].idx=idx;edge[len].next=adj[u];edge[len].t=v;adj[u]=&edge[len++];
}
void input()
{
int i;
for(i=0;i<m;i++)
{
scanf("%d%d",&e[i].u,&e[i].v);
e[i].idx=i;
if(e[i].u>e[i].v)
swap(e[i].u,e[i].v);
}
sort(e,e+m);
int flag=0;
for(i=0;i<m-1;i++)
{
if(e[i].u!=e[i+1].u||e[i].v!=e[i+1].v)
{
addedge(e[i].u,e[i].v,e[i].idx);
addedge(e[i].v,e[i].u,e[i].idx);
if(flag==1)
{
mm.insert(e[i].idx);
flag=0;
}
}
else
{
flag=1;
mm.insert(e[i].idx);
}
}
addedge(e[m-1].u,e[m-1].v,e[m-1].idx);
addedge(e[m-1].v,e[m-1].u,e[m-1].idx);
if(flag==1)
mm.insert(e[m-1].idx);
}
int v[maxn];
int dfsn[maxn];//時(shí)間戳
int low[maxn];//記錄它和它的子孫結(jié)點(diǎn)能夠到達(dá)的最小時(shí)間戳
int re[maxm*2];
int nAns;//記錄結(jié)果數(shù)目
int T=0;
void init(int n)
{
mm.clear();
nAns=0;
int i;
for(i=0;i<=n;i++)
adj[i]=NULL;
len=0;
}
void dfs(int fa,int x)//傳入樹的父親結(jié)點(diǎn)
{
v[x]=1;dfsn[x]=T;low[x]=T;T++;
node *p;
for(p=adj[x];p!=NULL;p=p->next)
{
if(p->t==fa)
continue;
int u=p->t;
if(!v[u])
{
dfs(x,u);
low[x]=min(low[x],low[u]);//注意是low值相比較，畫個(gè)圖很好理解
}
else if(u!=x)
low[x]=min(dfsn[u],low[x]);
}
}
int findAns=0;
void DfsFindPath(int fa,int x)
{
v[x]=1;
if(x==n-1)
{
findAns=1;
return;
}
node *p;
for(p=adj[x];p!=NULL;p=p->next)
{
if(!v[p->t])
{
DfsFindPath(x,p->t);
if(findAns==1)
{
if(low[p->t]>dfsn[x])
{
if(mm.find(p->idx)==mm.end())
re[nAns++]=p->idx;
}
return;
}
}
}
}
void FindBridge(int s)
{
T=0;
nAns=0;
memset(v,0,sizeof(v));
findAns=0;
dfs(-1,s);//注意第一個(gè)結(jié)點(diǎn)的父親用-1表示
memset(v,0,sizeof(v));
DfsFindPath(-1,s);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
input();
FindBridge(0);
sort(re,re+nAns);
printf("%d\n",nAns);
int i;
for(i=0;i<nAns;i++)
{
if(i>0)
printf(" ");
printf("%d",re[i]);
}
printf("\n");
}
return 0;
}