学步园

强连通裸题

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> ljb[200000],nljb[200000],jh[200000];
int n,m,i,x,y,wz,zn,ans,bcnt,dfn[200000],belong[200000],
instack[200000],low[200000],dindex,stap[200000],stop;
void tarjan(int i){
    dfn[i]=low[i]=++dindex;
    instack[i]=1;
    stap[++stop]=i;
    vector<int>::iterator iv;
    for (iv=ljb[i].begin();iv!=ljb[i].end();iv++){
        if (!dfn[*iv]){
            tarjan(*iv);
            if (low[*iv]<low[i])
                low[i]=low[*iv];
        }
        else if (instack[*iv]&&dfn[*iv]<low[i])
            low[i]=dfn[*iv];
    }
    if (dfn[i]==low[i]){
        bcnt++;
        int j;
        do{
            j=stap[stop--];
            instack[j]=0;
            belong[j]=bcnt;
            jh[bcnt].push_back(j);
        }
        while (j!=i);
    }
}
void work(){
    int i;
    for (i=1;i<=n;i++)
        if (!dfn[i])
            tarjan(i);
    printf("%d\n",bcnt);
}
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        while (x){
            ljb[i].push_back(x);
            scanf("%d",&x);
        }
    }
    
    work();
}