HU-169迷宮城（強連通重さ[Ksaraju]）

迷宮の城
http://acm.hdu.edu.cn/showproblem.php?pid=1269
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/32768 K（Java/Others）
Problem Description
希ちゃんの方向感覚を訓練するために、Gardonは大きなお城を建てました。中にはN部屋（N<=10000）とM通路（M<=100000）があります。どの通路も一方通行です。つまり、ある通路がA部屋とB部屋につながっているというなら、この通路を通ってA部屋からB部屋に行けるというだけですが、B部屋からA部屋に行けるとは説明していません。Gardonは、任意の2つの部屋が相互に接続されているかどうか手順を書いて確認してください。すなわち、任意のiとjに対しては、少なくとも1つの経路があり、部屋iから部屋jまでもあります。
 
Input
入力には複数のデータが含まれています。入力の最初の行は2つの数があります。NとM、次のM行はそれぞれ2つの数aとbがあります。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
   
   
   
   

まず一番簡単な強い連結成分のアルゴリズムを勉強します。
Korsarajuアルゴリズムは2回のdfsを必要とし、図を転置するが、線形時間でDAGのトポロジ順序を求めることができるようだ。
アルゴリズムを理解しました。
①原図をdfs（図がつながっていない可能性があります。）し、遍歴した点の出発時間を求めます。すなわち、出発時にスタックに入ります。
②転置図をdfsとし、開始点を出発時間から順に列挙（すなわち、最初のdfsに形成されたスタック）し、強連結成分＋1
③遍歴していない点がある場合（つまり、スタックに未遍歴の点がある場合）は、②
手でたたくと、感じはまあまあです。

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int n,m,s,e;
int stak[10005],top;//top          ，         
vector<int> edge[10005],edge_T[10005];
bool vis[10005];

void dfs(int u) {
    vis[u]=true;
    for(int i=0;i<edge[u].size();++i) {
        if(!vis[edge[u][i]])
            dfs(edge[u][i]);
    }
    stak[top++]=u;
}

void dfs_T(int u) {
    vis[u]=true;
    for(int i=0;i<edge_T[u].size();++i) {
        if(!vis[edge_T[u][i]])
            dfs_T(edge_T[u][i]);
    }
}

int Kosaraju() {
    int cnt=0;//       
    top=0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;++i)//      
        if(!vis[i])
            dfs(i);
    memset(vis,false,sizeof(vis));
    while(top>0) {
        s=stak[--top];
        if(!vis[s]) {
            dfs_T(s);
            ++cnt;//        +1
        }
    }
    return cnt;
}

int main() {
    while(scanf("%d%d",&n,&m),n!=0||m!=0) {
        for(int i=1;i<=n;++i) {
            edge[i].clear();
            edge_T[i].clear();
        }
        while(m-->0) {
            scanf("%d%d",&s,&e);
            edge[s].push_back(e);
            edge_T[e].push_back(s);
        }
        printf("%s
",Kosaraju()==1?"Yes":"No");
    }
    return 0;
}