学步园

Attack the NEET Princess

Time Limit:
9 Seconds      Memory Limit:

65536 KB

Houraisan Kaguya (
蓬萊山輝夜) is the
NEET (not in education, employment or training) princess living in Eientei
(
永遠亭). She is an unemployed geek, who sits at home and
surfs the Internet all day. But today is different, as the Hakurei Shrine
Reitaisai Festival (
博麗神社例大祭) will be hosted in Hakurei
Shrine
, Kaguya decides to go to buy some new doujin
games.

Fujiwara no Mokou (
藤原妹紅) detests
Kaguya, and has been planing to attack her for a long time. But she nerver got
the chance before because Kaguya kept staying in Eientei
, under the
protection of Yagokoro Eirin (
八意永琳). Knowing that
Kaguya will go outside today, Mokou decides to wait on certain road and attack
her once she passes there. Mokou don't know which path Kaguya will choose, but
she thinks that there always exits some roads where she can always meet Kaguya.

Input

There are multiple cases. Each case begins with two integers 2 ≤ n
≤ 10000 -- the number of villages and 2 ≤ m
≤ 100000 -- the number of
roads. Then m
lines, each contains two integers a
and b
(0
≤ a
, b
< n), indicating a road connecting village a
and
village b
. Village 0 is Eientei
and Village n
-1 is Hakurei
Shrine
. They are always connected by roads. There may be more than one
roads between two villages.

Output

Find out the roads where Mokou can always meet Kaguya. For each case,
output the number of roads in the first line, then output the numbers of the
roads in ascending order in the second line.

Sample Input

3 2

0 1

1 2

7 8

0 1

0 2

1 3

2 3

3 4

3 5

4 6

5 6

Sample Output

2

0 1

0

求起点到终点之间的必经之路
,
思路是
:
首先用
tarjan
算法求出图中的所有割边
,
然后从起点开始
BFS
到终点搜出一条路径
,
把路径上的边和已求出的割边求交集就可以得出必经之路
.

代码如下
:

 #include<stdio.h><br /> #include<string.h><br /> #include<stack><br /> #define MAXN 10005<br /> #include<algorithm><br /> using std::sort;<br /> using namespace std;<br /> struct E<br /> {<br /> int nod,db,cut,num;<br /> E *next;<br /> }head[MAXN*10];<br /> int low[MAXN],dfn[MAXN],res[10*MAXN],cnt;<br /> bool mark[MAXN],vis[MAXN];<br /> stack <int> ss;<br /> void tarjan(int u)<br /> {<br /> int v;<br /> E *p,*s,*q;<br /> low[u]=dfn[u]=cnt++;<br /> ss.push(u);<br /> vis[u]=1;<br /> mark[u]=1;<br /> for (p=head[u].next;p!=NULL;p=p->next)<br /> {<br /> v=p->nod;<br /> if (!mark[v])<br /> {<br /> if (!p->db)<br /> {<br /> s=head[v].next;<br /> q=&head[v];<br /> while (s->nod!=u) {q=s;s=s->next;}<br /> q->next=s->next;<br /> delete(s);<br /> }<br /> mark[v]=1;<br /> vis[v]=1;<br /> ss.push(v);<br /> tarjan(v);<br /> low[u]=min(low[u],low[v]);<br /> }<br /> else if (vis[v]) low[u]=min(low[u],dfn[v]);<br /> }<br /> if (low[u]==dfn[u])<br /> {<br /> while (!ss.empty()&&ss.top()!=u) ss.pop();<br /> ss.pop();<br /> }<br /> }<br /> bool DFS(int b,int e)<br /> {<br /> E *p;<br /> int v;<br /> if (b==e) return 1;<br /> p=head[b].next;<br /> while (p!=NULL)<br /> {<br /> v=p->nod;<br /> if (!mark[v])<br /> {<br /> if (DFS(v,e)==1)<br /> {<br /> if (p->cut==1) p->cut=2;<br /> return 1;<br /> }<br /> }<br /> }<br /> return 0;<br /> }<br /> bool find(int a,int b)<br /> {<br /> E *p;<br /> p=head[a].next;<br /> while (p!=NULL)<br /> {<br /> if (p->nod==b) return 1;<br /> p=p->next;<br /> }<br /> return 0;<br /> }<br /> int main()<br /> {<br /> int n,m,i,a,b,total;<br /> E *s,*p;<br /> while (scanf("%d%d",&n,&m)!=EOF)<br /> {<br /> memset(mark,0,sizeof(mark));<br /> memset(vis,0,sizeof(vis));<br /> memset(head,0,sizeof(head));<br /> for (i=1;i<=m;++i)<br /> {<br /> scanf("%d%d",&a,&b);<br /> a++;b++;<br /> if (!find(a,b))<br /> {<br /> s=new E;<br /> s->nod=b;<br /> s->db=0;<br /> s->cut=0;<br /> s->num=i;<br /> s->next=head[a].next;<br /> head[a].next=s;<br /> s=new E;<br /> s->nod=a;<br /> s->db=0;<br /> s->cut=0;<br /> s->num=i;<br /> s->next=head[b].next;<br /> head[b].next=s;<br /> }<br /> else<br /> {<br /> s=head[a].next;<br /> while (s!=NULL&&s->nod!=b) s=s->next;<br /> s->db=1;<br /> s=head[b].next;<br /> while (s!=NULL&&s->nod!=a) s=s->next;<br /> s->db=1;<br /> }<br /> }<br /> cnt=1;<br /> tarjan(1);<br /> for (i=1;i<=n;++i)<br /> {<br /> p=head[i].next;<br /> while (p!=NULL)<br /> {<br /> if (dfn[i]<low[p->nod]) p->cut=1;<br /> p=p->next;<br /> }<br /> }<br /> memset(mark,0,sizeof(mark));<br /> DFS(1,n);<br /> total=0;<br /> for (i=1;i<=n;++i)<br /> {<br /> p=head[i].next;<br /> while (p!=NULL)<br /> {<br /> if (p->cut==2) res[++total]=p->num;<br /> p=p->next;<br /> }<br /> }<br /> sort(res+1,res+total+1);<br /> printf("%d/n",total);<br /> for (i=1;i<=total;++i)<br /> {<br /> printf("%d",res[i]-1);<br /> if (i!=total) printf(" ");<br /> else printf("/n");<br /> }<br /> for (i=1;i<=n;++i)<br /> {<br /> p=head[i].next;<br /> s=p;<br /> while (s!=NULL)<br /> {<br /> s=s->next;<br /> delete(p);<br /> p=s;<br /> }<br /> }<br /> }<br /> return 0;<br /> }