题目描述

用强连通分量，缩点，把图转换成拓扑图。
找出度为0的点强连通分量里有多少点，强连通分量里的点都可以互相达到。
如果只有一个强连通分量的出度为0的话，答案就为这个强连通分量里点的数量，否则答案为0

参数说明

1. dfn[u]遍历到u的时间戳
2. low[u]从u开始走，所遍历到的最小时间戳
3. dfn[u]==low[u]表示u是其所在强连通分量的最高点

tarjan步骤

1. 先让当前点u的dfn和low等于时间戳
2. 使当前点入栈，记录当前点已在栈中
3. 遍历u所有邻点
4. 如果当前点未被遍历，则遍历该点tarjan(j)
5. 看一下u的邻点j所能到达的最小值，用这个最小值更新u的最小值
6. 若当前点j在栈当中，用j的时间戳dfn[j]直接更新u的low值，取min
7. 遍历完u之后，若dfn[u]==low[u],强连通分量cnt++
8. 取出栈顶元素y，标记该点从栈中出来
9. 标记该点属于哪一个强连通分量，id[y]=scc_cnt
10. 当y=u时，break，表示将该点所在的强连通分量处理完

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

const int N=10010,M=50010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timetp;
int st[N];

int id[N],scc_cnt,size_scc[N];
int dout[N];

stack<int> stk;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timetp;
    stk.push(u);
    st[u]=1;
    //遍历u的邻边
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(st[j])
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        scc_cnt++;
        int y;
        do{
            y=stk.top();
            stk.pop();
            st[y]=0;
            id[y]=scc_cnt;
            size_scc[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;
        }
    }
    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            zeros++;
            sum+=size_scc[i];
        }
        if(zeros>1)
        {
            sum=0;
            break;
        }
    }
    cout<<sum;


    return 0;
}

二刷，强连通分量的搜法：dfs

dfn[u]时间戳，就是按dfs遍历到这个点的次序
low[u]从u开始走，所遍历到的最小时间戳，也是这个强连通分量在树中的最高点，意味着回溯到这个点之后，不可能再遍历到该强连通分量中的任何一个点，因此用这个点代表一个强连通分量
栈代表当前未被搜完的强连通分量的所有点
j点在栈中 说明还没出栈 是dfs序比当前点u小的

注意 timetemp要从1开始，不能从0开始

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

const int N=10010,M=50010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timetp;
int st[N];

int id[N],scc_cnt,size_scc[N];
int dout[N];

stack<int> stk;

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timetp;
    stk.push(u);
    st[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(st[j])
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        scc_cnt++;
        int y;
        do{
            y=stk.top();
            stk.pop();
            st[y]=0;
            id[y]=scc_cnt;
            size_scc[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;
        }
    }

    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            zeros++;
            sum=size_scc[i];
        }
        if(zeros>1)
        {
            sum=0;
            break;
        }
    }
    cout<<sum;
    return 0;
}