迷宫城堡
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
Input
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
Output
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
Sample Output
Yes
No
No
Author
Gardon
Source
思路：最后belong所有点都为一个值则输出Yes;
否则输出No;(晚上看的缩点，明天开始看tarjan，洗洗睡吧）
缩点算法推荐：http://wenku.baidu.com/link?url=H6iQDzfiDht9cv8kyu0AjrpwDE6zxBKJKpGP-c1pqN2Uih1g9JzRuyw5cDanF76FNpUPg0WmqQW99VPcwDRcoT2qsGkrQ-aKFRdGpL6XfZm
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll __int64
#define inf 2000000001
int scan()
{
int res = , ch ;
while( !( ( ch = getchar() ) >= '' && ch <= '' ) )
{
if( ch == EOF ) return << ;
}
res = ch - '' ;
while( ( ch = getchar() ) >= '' && ch <= '' )
res = res * + ( ch - '' ) ;
return res ;
}
struct is
{
int u,v;
int next;
}edge1[],edge2[];
int flag1[],flag2[];
int jiedge1,jiedge2;
int jidian1,jidian2;
int head1[],head2[];
int shun1[],shun2[];
int belong[];
int n,m;
void update(int x,int y)
{
jiedge1++;
edge1[jiedge1].u=x;
edge1[jiedge1].v=y;
edge1[jiedge1].next=head1[x];
head1[x]=jiedge1;
jiedge2++;
edge2[jiedge2].u=y;
edge2[jiedge2].v=x;
edge2[jiedge2].next=head2[y];
head2[y]=jiedge2;
}
void dfs1(int x)
{
flag1[x]=;
for(int i=head1[x];i;i=edge1[i].next)
{
if(!flag1[edge1[i].v])
dfs1(edge1[i].v);
}
shun1[++jidian1]=x;
}
void dfs2(int x)
{
flag2[x]=;
belong[x]=jidian2;
for(int i=head2[x];i;i=edge2[i].next)
{
if(!flag2[edge2[i].v])
dfs2(edge2[i].v);
}
}
void Kosaraju()
{
memset(flag1,,sizeof(flag1));
memset(flag2,,sizeof(flag2));
jidian1=;
for(int i=;i<=n;i++)
if(!flag1[i])
dfs1(i);
jidian2=;
for(int i=jidian1;i>;i--)
{
if(!flag2[shun1[i]])
{
dfs2(shun1[i]);
jidian2++;
}
}
}
int main()
{
int i;
while(~scanf("%d%d",&n,&m))
{
memset(head1,,sizeof(head1));
memset(head2,,sizeof(head2));
if(n==&&m==)break;
jiedge1=;
jiedge2=;
for(i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
update(u,v);
}
Kosaraju();
for(i=;i<=n;i++)
printf("%d ",belong[i]);
cout<<endl;
int lu=,ans=belong[];
for(i=;i<=n;i++)
if(belong[i]!=ans)
{
lu=;
break;
}
if(lu)
printf("No\n");
else
printf("Yes\n");
}
return ;
}