HDU 1269移動城連通成分Tarjan

迷宮の城
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8211    Accepted Submission(s): 3669
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 <stdio.h>

#include <string.h>

#include <vector>

#include <stack>

#define MIN(a,b) ((a)<(b)?(a):(b))

#define N 10005

using namespace std;

 

stack<int>sta;

vector<int>gra[N];

int dfn[N],low[N],now,vis[N],sum;

int n,m;

 

void ini(void)

{

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(vis,0,sizeof(vis));

    now=sum=0;

    for(int i=1;i<=n;i++)

        gra[i].clear();

    while(sta.empty()==0)

        sta.pop();

}

 

void tarjan(int s)

{

    vis[s]=2;

    dfn[s]=low[s]=++now;

    sta.push(s);

    for(int i=0;i<gra[s].size();i++)

    {

        int t=gra[s][i];

        if(!dfn[t])

            tarjan(t),low[s]=MIN(low[s],low[t]);

        else

            if(vis[t]==2)

                low[s]=MIN(low[s],dfn[t]);

    }

    if(low[s]==dfn[s])

    {

        sum++;

        while(!sta.empty())

        {

            int t=sta.top();

            sta.pop();

            vis[t]=1;

            if(t==s)break;

        }

    }

}

 

void re(void)

{

    for(int i=1;i<=m;i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        gra[a].push_back(b);

    }

}

 

void run(void)

{

    for(int i=1;i<=n;i++)

        if(!dfn[i])

            tarjan(i);

    if(sum>1)

        puts("No");

    else

        puts("Yes");

}

 

int main()

{

    while(scanf("%d%d",&n,&m),n+m)

    {

        ini();

        re();

        run();

    }

}