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;
}