强连通分量/缩点（POJ1236）

洛谷P2002

书P416

例题：https://ac.nowcoder.com/acm/contest/1061/A

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
struct edge
{
    int to,nxt;
}e[maxn*maxn];
int head[maxn],low[maxn],dfn[maxn],sta[maxn],belong[maxn],vis[maxn],num[maxn],rd[maxn],cd[maxn];
int en,top,scc,n,m,Index;
void addedge(int u,int v)
{
    e[en].to=v;
    e[en].nxt=head[u];
    head[u]=en++;
}
void tarjan(int x)
{
    int v;
    dfn[x]=low[x]=++Index;
    sta[top++]=x;
    vis[x]=1;
    for(int i=head[x];i!=-1;i=e[i].nxt)
    {
        v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else
            if(vis[v])
            {
                low[x]=min(low[x],dfn[v]);
            }
    }
    if(low[x]==dfn[x])
    {
        scc++;
        do
        {
            v=sta[--top];
            vis[v]=0;
            belong[v]=scc;
            num[scc]++;
        }while(x!=v);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    memset(head,-1,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(rd,0,sizeof(rd));
    memset(cd,0,sizeof(cd));
    memset(num,0,sizeof(num));
    top=0;
    Index=0;
    scc=0;
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            int v;
            cin>>v;
            if(v==0) break;
            addedge(i,v);
        }
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int u=1;u<=n;u++)
        for(int i=head[u];i!=-1;i=e[i].nxt)
        {
            int v=e[i].to;
            if(belong[u]!=belong[v])
            {
                cd[belong[u]]++;
                rd[belong[v]]++;
            }
 
        }
    int ans1=0,ans2=0;
    for(int i=1;i<=scc;i++)
        if(rd[i]==0) ans1++;
    for(int i=1;i<=scc;i++)
        if(cd[i]==0) ans2++;
    if(scc==1) cout<<1<<endl;
    else cout<<ans1<<endl;
    return 0;
}

来源：https://blog.csdn.net/qq_40642465/article/details/81410110