hdu1269迷宮城堡 (強連通Tarjan+鄰接表)

Problem Description 為了訓練小希的方向感，Gardon建立了一座大城堡，裡面有N個房間(N<=10000)和M條通道(M<=100000)，每個通道都是單向的，就是說若稱某通道連通了A房間和B房間，只說明可以通過這個通道由A房間到達B房間，但並不說明通過它可以由B房間到達A房間。Gardon需要請你寫個程序確認一下是否任意兩個房間都是相互連通的，即：對於任意的i和j，至少存在一條路徑可以從房間i到房間j，也存在一條路徑可以從房間j到房間i。

Input 輸入包含多組數據，輸入的第一行有兩個數：N和M，接下來的M行每行有兩個數a和b，表示了一條通道可以從A房間來到B房間。文件最後以兩個0結束。

Output 對於輸入的每組數據，如果任意兩個房間都是相互連接的，輸出"Yes"，否則輸出"No"。

Sample Input

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

Yes
No

#include
#include
#include
using namespace std;
typedef struct nnn
{
    int u;
    struct nnn *next;
}*List,list;

List linkList[10005];
int stack[10005],sn;
int dfn[10005],low[10005],vist[10005],deep,flog,n;
void addNode(List &p,int uu)
{
        List q=(List)malloc(sizeof(list));
        q->u=uu;
        q->next=p->next;
        p->next=q;
}
void DFS(int v)
{
    List p=linkList[v]->next;
    deep++; vist[v]=1;
    stack[++sn]=v;
    dfn[v]=low[v]=deep;

    while(p!=NULL)
    {
        int u=p->u;
        if(vist[u]==0)
        {
            DFS(u);
            low[v]=(low[v]next;
    }
    if(low[v]==dfn[v])//表示在棧中的當前點到棧頂的點組成一個強連通
    {
        if(v!=1)flog=1;//如果v!=1表明可能有多個強連通
        else if(sn!=n)flog=1;//v=1了但是這個強連通中點的個數為sn個
    }
}
int main()
{
    int m,v,u;
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        for(int i=1; i<=n; i++)
        {
            linkList[i]=(List)malloc(sizeof(list));
            vist[i]=0; linkList[i]->next=NULL;
        }
        while(m--)
        {
            scanf("%d%d",&v,&u);
            addNode(linkList[v],u);
        }
        flog=0; deep=0; sn=0;
        DFS(1);
        if(flog)printf("No\n");
        else printf("Yes\n");
    }
}