hdu 1269のtarjan

迷宮の城
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6359    Accepted Submission(s): 2835
Problem Description
希ちゃんの方向感覚を訓練するために、Gardonは大きな城を建てました.中にはN部屋(N<=10000)とM通路(M<=10000)があり、各通路は一方向です.つまり、ある通路がA部屋とB部屋につながっているとすれば、この通路を通ってA部屋からB部屋に着くことができることを説明するだけですが、B部屋からA部屋に着くことは説明しません.Gardonは、任意のiとjに対して、少なくとも1つの経路が部屋iから部屋jまで、1つの経路が部屋jから部屋iまでつながっているかどうかを確認するプログラムを書く必要があります.
 
Input
入力には複数のデータのセットが含まれ、入力された最初の行にはNとMの2つの数があり、次のM行には1行あたり2つの数aとbがあり、1つのチャネルがA部屋からB部屋に来ることができることを示している.ファイルは最後に2つの0で終了します.
 
Output
入力された各グループのデータについて、いずれの部屋も互いに接続されている場合は「Yes」を出力し、そうでない場合は「No」を出力します.
 
Sample Input

   
   
   
   

    
    
    
    3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Yes
No
   
   
   
   
   
   
   
   


   
   
   
   

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;

const int MAX=10000+10;
int n,m,size,Index,sum;
int head[MAX],dfn[MAX],low[MAX];//dfn         ,low            (    ) 

struct Edge{
	int v,next;
	Edge(){}
	Edge(int V,int NEXT):v(V),next(NEXT){}
}edge[MAX*10];

void Init(int num){
	for(int i=0;i<=num;++i)head[i]=-1,dfn[i]=0;
	size=Index=sum=0;
}

void InsertEdge(int u,int v){
	edge[size]=Edge(v,head[u]);
	head[u]=size++;
}

void tarjan(int u){
	if(dfn[u])return;//     u      
	dfn[u]=low[u]=++Index;
	for(int i=head[u];i != -1;i=edge[i].next){
		int v=edge[i].v;
		tarjan(v);
		low[u]=min(low[u],low[v]);
	}
}

int main(){
	int u,v;
	while(~scanf("%d%d",&n,&m),n+m){
		Init(n);
		for(int i=0;i<m;++i){
			scanf("%d%d",&u,&v);
			InsertEdge(u,v);
		}
		tarjan(1);//dfs,                ,                   ,             ,                  
		for(int i=1;i<=n;++i)if(dfn[i] == low[i] || !dfn[i])++sum;//              (          ,sum  >1)
		if(sum == 1)printf("Yes
");
		else printf("No
");
	}
	return 0;
}
/*
5 6
1 2
2 3
3 5
3 4
4 2
5 1
*/