[Tarjan 有向图强连通分量]ural 1198：Jobbery

大致题意：
? 给出一个有向图，求图中是否存只在一个入度为0的强联通分量，存在的话输出这个分量中的所有点。否则只输出一个 0.

?

大致思路：
? ? Tarjan缩点，后对所有强连通分量求出入度出度~~

?

#include<iostream>#include<cstdio>#include <algorithm>#include<cstring>using namespace std;const int inf=1<<30;const int nMax=3015;const int mMax=5001000;class edge{public:    int v,nex;};edge e[mMax];int k,head[nMax];//head[i]是以点i为起点的链表头部void addedge(int a,int b){//向图中加边的算法，注意加上的是有向边//b为a的后续节点既是a---->b    e[k].v=b;    e[k].nex=head[a];    head[a]=k;k++;}int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep;   //atype 强连通分量的个数bool insta[nMax];void Tarjan(int u){                 //我的Tarjan模版    int i,j;    dfn[u]=low[u]=++dep;    sta[++top]=u;    insta[u]=1;    for(i=head[u];i;i=e[i].nex){        int v=e[i].v;        if(!dfn[v]){            Tarjan(v);            low[u]=min(low[u],low[v]);        }        else{            if(insta[v])low[u]=min(low[u],dfn[v]);        }    }    if(dfn[u]==low[u]){        atype++;              //强连通分量个数        do{            j=sta[top--];            belon[j]=atype;   //第j个点属于第type个连通块            insta[j]=0;        }while(u!=j);    }}int out[nMax];        //每个连通块的出度int in[nMax];void init(){    k=1;    dep=1;    top=atype=0;    memset(insta,0,sizeof(insta)); //是否在栈中    memset(head,0,sizeof(head));   //静态链表头指针    memset(low,0,sizeof(low));     //Tarjan的low数组    memset(dfn,0,sizeof(dfn));     //Tarjan的dfn数组    memset(out,0,sizeof(out));     //记录每个强连通分量的出度    memset(in,0,sizeof(in));       //记录每个强连通分量的入度    memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量}int main(){    int t,n,m,i,j,a,b,tmp,sum,inum,onum;    while(scanf("%d",&n)!=EOF){        init();        inum=onum=0;        for(i=1;i<=n;i++){            while(scanf("%d",&m)&&m){                addedge(i,m);            }        }        for(i=1;i<=n;i++){            if(!dfn[i])Tarjan(i);        }        for(i=1;i<=n;i++){            tmp=belon[i];            for(j=head[i];j;j=e[j].nex){                int v=e[j].v;                if(belon[i]!=belon[v]){                    out[tmp]++;                    in[belon[v]]++;                }            }        }        for(i=1;i<=atype;i++){            if(in[i]==0){                tmp=i;                inum++;            }        }        if(inum!=1){            printf("0\n");        }        else{            for(i=1;i<=n;i++){                if(belon[i]==tmp){                    printf("%d ",i);                }            }            printf("0\n");        }    }    return 0;}