Codeforces

分析

一个结论：拓扑排序时，任意时刻同时在队列中的两个点不能互相到达。

设已经访问到的点数为 $tot$，那么

• 如果队列中只有 $u$ 一个点，那么它可以到达剩下的 $n-tot$ 个点。
• 如果队列中有 $u,x$ 两个点，那么首先 $u$ 不能到达 $x$；其次如果 $x$ 的出边中有一个点 $v$ 入度为 $1$，则 $u$ 一定无法到达那个点，那么 $u$ 就不满足条件了。否则，$u$ 可以到达除 $x$ 之外的 $n-tot-1$ 个点。
• 如果队列中有 $>2$ 个点，那么 $u$ 一定不满足条件。

这样子求出了可能满足条件的点能到达的点数，在反图上再跑一遍即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,m,x[N],y[N],deg[N],s[N];
vector<int> E[N];
queue<int> Q;

void Topsort() {
    int tot=0;
    for (int i=1;i<=n;i++) if (!deg[i]) Q.push(i);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); ++tot;
        if (Q.empty()) s[u]+=n-tot;
        else if (Q.size()==1) {
            int x=Q.front(),flag=0;
            for (int v:E[x]) if (deg[v]==1) { flag=1; break; }
            if (!flag) s[u]+=n-tot-1;
        }
        for (int v:E[u]) if (!--deg[v]) Q.push(v);
    }
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=m;i++) x[i]=read(),y[i]=read();
    for (int i=1;i<=m;i++) E[x[i]].emplace_back(y[i]),++deg[y[i]];
    Topsort();
    for (int i=1;i<=n;i++) E[i].clear(),deg[i]=0;
    for (int i=1;i<=m;++i) E[y[i]].emplace_back(x[i]),++deg[x[i]];
    Topsort();
    int ans=0;
    for (int i=1;i<=n;++i) if (s[i]>=n-2) ++ans;
    printf("%d\n",ans);
    return 0;
}