所谓0->n-1路径上一定要经过的割边，就是0->n-1任意一条路径上的割边，因为割边是必经之路。其实这题跟ZOJ 2588是同一个题，稍微变化就可以得到答案了，不过这题我当时的模板貌似写挫了，对边进行判重的时候进行了暴力，其实可以用set存一下，那么查找的复杂度可以降到log(n).
具体求割边的方法可以看这个：
http://www.cppblog.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;//存储重边
int const maxn=10010;//顶点数
int const maxm=100010;//边数
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];//时间戳
int low[maxn];//记录它和它的子孙结点能够到达的最小时间戳
int re[maxm*2];
int nAns;//记录结果数目
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)//传入树的父亲结点
{
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值相比较，画个图很好理解
}
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);//注意第一个结点的父亲用-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;
}