Tarjan算法求强联通分量

强联通分量模板题.
当然,你需要知道什么是强联通分量,以及怎么求强联通分量

先用Tarjan算法求强联通分量.
再记录新图上每个点的出度,再找出初度为0的点,如果只有一个,直接加上该强联通分量的大小.
大于一的话答案即为0.

时间复杂度 $O(n+m)$

C++ 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 10010
#define M 50010
using namespace std;
struct node{
    int to,next;
}e[M];
stack<int> s;
vector<int> scc[N];
int tot,head[N];
int n,m,cnt,num;
int dfn[N],low[N],id[N],dout[N];
bool ins[N];
inline void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++num;
    s.push(u),ins[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        int v;
        do{
            v=s.top(),s.pop();
            ins[v]=0;
            id[v]=cnt,scc[cnt].push_back(v);
        }while(v!=u);
    }
}
int main()
{
    //freopen(".in","r",stdin),freopen(".out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,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;i=e[i].next){
            int v=e[i].to;
            if(id[u]!=id[v])
                dout[id[u]]++;
        }
    int zeros=0,ans=0;
    for(int i=1;i<=cnt;i++)
        if(!dout[i]){
            zeros++;
            ans+=scc[i].size();
            if(zeros>1){
                ans=0;
                break;
            }
        }
    printf("%d\n",ans);
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/