思路和这个CF差不多 CF题目

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
#define PII pair<int,int>
#define int long long
//#define int __int128
using namespace std;
const int inf = 2e18;
const int N = 3e6 + 10;

vector<int> g[N];
vector<int> G[N];
vector<PII> e;
int in[N];
int f[N];//f[x]表示x能到的点数 + 能到x的点数
bool st[N];//这个点无法到y，也无法到z
int n, m;


int dfn[N], low[N];//dfs序的俩数组
stack<int> s;
int ins[N];//是否走过
int sz[N];//强连通分量里面有几个点
int cnt, sccn;
int scc[N];//强连通分量
void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    s.push(u);
    ins[u] = 1;

    for (auto v : g[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }

    if (low[u] == dfn[u])//栈里面有父子关系，从最上面到u是一个scc（强连通分量）
    {
        ins[u] = 0;
        scc[u] = ++sccn;
        sz[sccn] = 1;
        while (s.top() != u)
        {
            scc[s.top()] = sccn;//sccn是强连通分量的标号 
            sz[sccn]++;
            ins[s.top()] = 0;
            s.pop();
        }
        s.pop();
    }
}


void topsort()
{
    queue<int> q;
    int tot = 0;
    for (int i = 1; i <= sccn; i++)
        if (!in[i])
            q.push(i), tot++;

    while (q.size())
    {
        auto t = q.front();
        int num = q.size();
        q.pop();
        
        //cout<<num<<' '<<t<<endl;
        if (num == 1) f[t] += n - tot;

        for (auto v : G[t])
        {
            in[v]--;
            if (!in[v]) q.push(v), tot++;
        }
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 0, a, b; i < m; i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        e.push_back({ a,b });
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
            
    //cout<<sccn<<endl;

    for (int i = 0; i < m; i++)
    {
        int a = e[i].first, b = e[i].second;
        if (scc[a] != scc[b]) 
        {
            G[scc[a]].push_back(scc[b]);
            in[scc[b]]++;
        }
    }

    topsort();

    for (int i = 1; i <= n; i++) G[i].clear();

    for (int i = 0; i < m; i++)
    {
        int a = e[i].first, b = e[i].second;
        if (scc[a] != scc[b])
        {
            G[scc[b]].push_back(scc[a]);
            in[scc[a]]++;
        }
    }

    topsort();
    
    // for(int i=1;i<=sccn;i++)
    //     cout<<f[i]<<" ";
    // cout<<endl;

    int ans = 0;
    for (int i = 1; i <= sccn; i++)
        if (f[i] == sccn - 1)
            ans += sz[i];

    cout << ans << endl;
}

signed main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}