迷宫城堡
time limit per test 1 second memory limit per test 256 megabytes
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

传送门：HDU1269

Input

输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

Output

对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。

Sample Input

1
2
3
4
5
6
7
8
9
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0

Sample Output

1
2
Yes
No

题解

裸的求强联通分量个数 抄了一波tarjan模板
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.io.*;  
import java.util.*;  
public class Main {  
  
    public static void main(String[] args) {  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        Tarjan tar=new Tarjan();  
        while(sc.hasNext()){  
            int n=sc.nextInt();  
            int m=sc.nextInt();  
            if(n==0&&m==0)break;  
            tar.init();  
            for(int i=0;i<m;i++){  
                int u=sc.nextInt();  
                int v=sc.nextInt();  
                tar.add_diredge(u, v, 1);  
            }  
            for(int i=1;i<=n;i++){ //需要对每个点tarjin一次(如果没被访问过)  
                if(tar.dfn[i]==0){  
                    tar.tarjan(i);  
                }  
            }  
            if(tar.bcount>=2){  
                pw.println("No");  
            }else{  
                pw.println("Yes");  
            }  
            pw.flush();  
        }  
  
    }  
  
}  
class Tarjan{  
    ArrayList<Edge>[]adj; //邻接表  
    int top;  
    int[] stack;  
    boolean[] instack; //点是否在栈里  
    int[]dfn; //访问的次序  
    int[]low;  
    int[]belong; //点属于哪个强联通分量  
    int bcount; //强联通分量的个数  
    int dindex; //时间戳  
    int maxn=100100;  
    Tarjan(){  
        adj=new ArrayList[maxn];  
        for(int i=0;i<maxn;i++)adj[i]=new ArrayList<Edge>();  
        stack=new int[maxn];  
        instack=new boolean[maxn];  
        dfn=new int[maxn];  
        low=new int[maxn];  
        belong=new int[maxn];  
    }  
    void init(){  
        for(int i=0;i<maxn;i++)adj[i].clear();  
        top=0;  
        bcount=0;  
        dindex=0;  
        Arrays.fill(dfn, 0);  
    }  
    void tarjan(int u){  
        dfn[u]=low[u]=++dindex;  
        stack[++top]=u;  
        instack[u]=true;  
        for(int i=0;i<adj[u].size();i++){  
            int v=adj[u].get(i).v;  
            if(dfn[v]==0){  
                tarjan(v);  
                low[u]=Math.min(low[u], low[v]);  
            }else if(instack[v]&&dfn[v]<low[u]){  
                low[u]=dfn[v];  
            }  
        }  
        if(dfn[u]==low[u]){  
            bcount++;  
            int v;  
            do{  
                v=stack[top--];  
                instack[v]=false;  
                belong[v]=bcount;  
            }while(u!=v);  
        }  
    }  
    void add_diredge(int u, int v, int c){  
        adj[u].add(new Edge(u,v,c));  
    }  
}  
class Edge{  
    int u;  
    int v;  
    int w;  
    Edge(int u,int v,int w){  
        this.u=u;  
        this.v=v;  
        this.w=w;  
    }  
}