Link

Sol

球：拓扑排序是一个黑箱操作是吧？就是你根本不知道它在干什么，但是我们可以想一想拓扑排序的“黑箱”有什么性质

拓扑排序的“黑箱”队列的性质，一个点能进队列，当且仅当他的前驱节点都已出队。在一张DAG上，若两个点同时出现在队列中，那么他们互相无法到达，否则不是DAG。因为两个点在没有环的前提下能互相到达，只能是从相同的前驱过来。能同时出现在队列中说明没有这样的前驱节点。

我们记 $f_i$ 表示从该点可以走到的点集和可以走到该点的点集的并集大小。分开处理该点可以走到的点和可以走到该点的点，只要建出反图做相同的操作即可。

以在正图上的情况做说明，反图的情况同理可得

先来算算重要节点。加入在一个队列里面，假如现在队列里面只有它一个点$i$，那么它可以到的点就是除它意外的所有$n-1$个点。这样对$f_i$的贡献就是$n-tot$ . $tot$ 指的是拓扑开始前就入队的点的个数。

那么次重要节点的计算也很简单。次重要节点要成为重要节点，当且仅当队列中元素个数为$2$时，设这两个点分别为$u,v$， 在$u$到$v$的路径上只要存在一个点的入度为$1$，那么这个点被删除之后这两个点中的任意一者即满足条件。把贡献记到任意一个点上，给另外一个点打上标记即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 3e5 + 5;

int n, m, num;
int head[SIZE], deg[SIZE], vis[SIZE], f[SIZE], cx[SIZE], cy[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void calc(int u, int to, int w) {
    int flag = 0;
    for (int i = head[to], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (deg[v] == 1) { flag = 1; break; }
    }
    if (flag) vis[u] = 1;
    else f[u] += w;
}

void top() {
    int cnt = 0;
    std::queue < int > q;
    for (int i = 1; i <= n; ++ i) {
        if (!deg[i]) q.push(i), ++ cnt;
    }
    while (!q.empty()) {
        int u = q.front(), siz = q.size(); q.pop();
        if (siz == 1) f[u] += n - cnt;
        else if (siz == 2) calc(u, q.front(), n - cnt);
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to, -- deg[v];
            if (!deg[v]) q.push(v), ++ cnt;
        }
    }
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read();
    for (int i = 1; i <= m; ++ i) {
        cx[i] = read(), cy[i] = read();
        addEdge(cx[i], cy[i]); ++ deg[cy[i]];
    }
    top();
    num = 0; memset(head, 0, sizeof(head)); memset(deg, 0, sizeof(deg));
    for (int i = 1; i <= m; ++ i) {
        addEdge(cy[i], cx[i]), ++ deg[cx[i]];
    }
    top();
    int res = 0;
    for (int i = 1; i <= n; ++ i) {
        if (!vis[i] && f[i] >= n - 2) ++ res;
    }
    printf("%d\n", res);
    return 0;
}