强连通分量

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=5e4+5;
int n,m,cnt,top,fro[N],s[N];
int tot,color,dfs[N],low[N],col[N],size[N],in[N];
struct edge{int to,nxt;}e[M];
void add(int x,int y) {
    e[++cnt]={y,fro[x]}; fro[x]=cnt;
}

void Tarjan(int u) {
    dfs[u]=low[u]=++tot;
    s[++top]=u;
    for(int i=fro[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(!dfs[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!col[v])
         low[u]=min(low[u],dfs[v]);
    }
    if(low[u]==dfs[u]) {
        col[u]=++color;
        while(s[top]!=u) {
            col[s[top--]]=color;
            size[color]++;
        }
        top--,size[color]++;
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++) 
     scanf("%d%d",&a,&b),add(b,a); //反向建边，统计出度变为统计入度 
    for(int i=1;i<=n;i++) 
     if(!dfs[i]) Tarjan(i);
     
    for(int i=1;i<=n;i++)
     for(int j=fro[i];j;j=e[j].nxt)
      if(col[i]!=col[e[j].to]) 
       in[col[e[j].to]]++;
    int ans=-1;
    for(int i=1;i<=color;i++)
     if(!in[i]) ans=~ans?0:size[i];
    printf("%d",ans);    
}