HDU 1269迷宮城(強連通tarjan)

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

/********************************************************************************
*     ：Tarjan                ，
*                  。   ，                   ，
*                          。
*   :  DFN(u)   u       (   )，Low(u) u u        
*             。
*   ： DFN(u)=Low(u) ， u                    。
* Low(u)=Min
* {
* DFN(u),
* Low(v),(u,v)    ，u v    
* DFN(v),(u,v)           (    )
* }
*
*   ：tarjan   
* Problem：HDU1269    
* author：crazy_  
* date: 2013/09/07
*********************************************************************************/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define A system("pause")

using namespace std;

const int maxn=10000+5;

struct Node
{
    int v,next;
}edge[maxn*10];

int dfn[maxn],low[maxn];
bool instack[maxn];
int stack[maxn];
int head[maxn];

int top,Bcnt,index;
int cnt;

int n,m;

void addedge(int u,int v)
{
     edge[cnt].v=v;
     edge[cnt].next=head[u];
     head[u]=cnt++;
}

void tarjan(int u)
{
     int v;
     dfn[u]=low[u]=++index;
     instack[u]=true;
     stack[++top]=u;

     for(int i=head[u];~i;i=edge[i].next)//     ；
     {
         v=edge[i].v;//      ；
         if(!dfn[v])//      ，     ；
         {
             tarjan(v);
             low[u]=min(low[u],low[v]);//  ；
         }
         else if(instack[u])
         {
             low[u]=min(dfn[v],low[u]);//   ；
         }
     }
     if(dfn[u]==low[u])
     {
         Bcnt++;
         do
         {
             v=stack[top--];
             instack[v]=false;
         }while(v!=u);
     }
}

void solve()
{
     int i;
     top=index=Bcnt=0;
     memset(instack,0,sizeof(instack));
     memset(dfn,0,sizeof(dfn));

     for(i=1;i<=n;i++)
     {
        if(!dfn[i])
         tarjan(i);
     }
     if(Bcnt==1)
         puts("Yes");
     else
         puts("No");
}

int main()
{
     while(scanf("%d%d%*c",&n,&m)!=EOF)
     {
         if(n==0&&m==0)
            break;

         cnt=0;
         memset(head,-1,sizeof(head));

         for(int i=0;i<m;i++)
         {
             int a,b;
             scanf("%d%d",&a,&b);
             addedge(a,b);
         }

         solve();
     }
     return 0;
}
/*PS:       WA   tarjan(i)   tarjan[i],      。。。。  byvoid  ！*/