poj 1904 King's Quest 强联通分量

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int head[40005],nume;
int insta[40005],sta[40005],low[40005],dfn[40005],atype,dep,top,belon[40005];
struct node
{
    int v,nxt;
};
struct node e[4000000];

void add(int v,int u)
{
    e[nume].v=u;e[nume].nxt=head[v];head[v]=nume;
    nume++;
}
void Tarjan(int u)
{
    int i,j;
    dfn[u]=low[u]=++dep;
    insta[u]=1;
    sta[++top]=u;
    for(i=head[u];i;i=e[i].nxt){
        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;
            insta[j]=0;
        }while(u!=j);
    }
}
int main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF){
        top=atype=0;
        nume=dep=1;
        memset(head,0,sizeof(head));
        memset(insta,0,sizeof(insta));
       // memset(sta,0,sizeof(sta));
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(belon,0,sizeof(belon));
        for(i=1;i<=n;i++){
            int k;
            scanf("%d",&k);
            for(j=1;j<=k;j++){
                int u;
                scanf("%d",&u);
                add(i,n+u);
            }
        }
        for(i=1;i<=n;i++){
            int v;
            scanf("%d",&v);
            add(n+v,i);
        }
       for(i=1;i<=2*n;i++){
            if(!dfn[i])
                Tarjan(i);
       }
       int ans[2005];
       for(i=1;i<=n;i++){
            int temp=0;
            for(j=head[i];j;j=e[j].nxt){
                int v=e[j].v;
                if(belon[i]==belon[v]){
                    ans[temp++]=v-n;
                }
            }
            sort(ans,ans+temp);
            printf("%d",temp);
            for(j=0;j<temp;j++) printf(" %d",ans[j]);
            printf("\n");
       }
    }
}

poj 1904 King's Quest 强联通分量,,5-wow.com