首页 > 代码库 > hdu1269 Tarjan强连通分量 模板(转)

hdu1269 Tarjan强连通分量 模板(转)

#include<stdio.h>#include<iostream>#include<vector>using namespace std;const int maxn=10010;vector<int>g[maxn];int Bcnt;int Top;int Index;int low[maxn],dfn[maxn];int belong[maxn],stack[maxn];int instack[maxn];void Init_tarjan(int n){    Bcnt=Top=Index=0;    for(int i=0;i<=n;i++)        low[i]=dfn[i]=0;}void Tarjan(int u){    stack[Top++]=u;    instack[u]=1;    low[u]=dfn[u]=++Index;    for(int i=0;i<g[u].size();i++)    {        int v=g[u][i];        if(!dfn[v])        {            Tarjan(v);            low[u]=min(low[v],low[u]);        }        else        {            if(instack[v])                low[u]=min(low[u],dfn[v]);        }    }    if(low[u]==dfn[u])    {        ++Bcnt;        int v;        do        {            v=stack[--Top];            instack[v]=0;            belong[v]=Bcnt;        }        while(u!=v);    }}int main(){    int n,m;    int i;    int x,y;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0&&m==0)break;        for(i=1;i<=n;i++)            g[i].clear();        while(m--)        {            scanf("%d %d",&x,&y);            g[x].push_back(y);        }        Init_tarjan(n);        for(i=0;i<=n;i++)        {            if(!dfn[i])                Tarjan(1);        }        if(Bcnt==1)printf("Yes\n");        else printf("No\n");    }    return 0;}