SCC之tarjan算法入门[HDU 1269]

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
const int maxn=10001;  
struct node{  
    int e,next;  
}mpt[maxn*10];  
int head[maxn];  
int n,m,k;  
int low[maxn];  
int dfn[maxn];  
int vis[maxn];  
int que[maxn];  
int cnt,index,top;  
void add(int s,int t){  
    mpt[k].e=t;  
    mpt[k].next=head[s];  
    head[s]=k++;  
}  
void tarjan(int s){  
    low[s]=dfn[s]=++index;  
    que[++top]=s;  
    vis[s]=1;  
    for(int i=head[s];i!=-1;i=mpt[i].next){  
        int e=mpt[i].e;  
        if(!dfn[e]){  
            tarjan(e);  
            low[s]=min(low[s],low[e]);  
        }  
        else if(vis[e]){  
            low[s]=min(low[s],dfn[e]);  
        }  
    }  
    if(low[s]==dfn[s]){  
        cnt++;  
        int e;  
        do{  
            e=que[top--];  
            vis[e]=0;  
        }while(s!=e);  
    }  
}  
void init(){  
    memset(head,-1,sizeof(head));  
    memset(dfn,0,sizeof(dfn));  
    memset(vis,0,sizeof(vis));  
    cnt=k=index=0;  
    top=-1;  
}  
int main(){  
    int n,m;  
    while(scanf("%d%d",&n,&m)!=EOF){  
        if(n==0&&m==0)break;  
        init();  
        int a,b;  
        for(int i=0;i<m;i++){  
            scanf("%d%d",&a,&b);  
            add(a,b);  
        }  
        for(int i=1;i<=n;i++){  
            if(!dfn[i])  
                tarjan(i);  
        }  
        if(cnt==1)printf("Yes\n");  
        else printf("No\n");  
    }  
    return 0;  
}