「ZROI」奖牌的统计

题目大意：$n$ 个元素，$m$ 条形如 $x$ 大于 $y$ 的关系，请你输出前三大的元素有多少种可能。$n \leq 10^5, m \leq 2 \times 10^5$

拓扑排序，分类讨论一级顶点、二级顶点、三级顶点的情况。

#include <cstdio>
#include <algorithm>

const int N = 100005;
struct Edge {
	int u, v;
	bool operator < (const Edge &rhs) const {
		if (u == rhs.u) return v < rhs.v;
		return u < rhs.u;
	}
} e[N<<1];
int head[N], nxt[N<<1], pnt[N<<1], tot;
int sta1[N], top1, sta2[N], top2, dgr[N], tag[N];
long long ans;

int read() {
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x;
}
void add_edge(int u, int v) {
	nxt[++tot] = head[u];
	head[u] = tot, pnt[tot] = v;
}

int main() {
	int n = read(), m = read();
	for (int i = 1; i <= m; ++i)
		e[i].u = read(), e[i].v = read(); 
	std::sort(e + 1, e + m + 1);
	for (int i = 1; i <= m; ++i)
		if (e[i].u != e[i-1].u || e[i].v != e[i-1].v)
			add_edge(e[i].u, e[i].v), ++dgr[e[i].v];
	for (int i = 1; i <= n; ++i)
		if (dgr[i] == 0) sta1[++top1] = i;
	ans += 1LL * top1 * (top1 - 1) * (top1 - 2); //三个点均为一级顶点
	for (int i = 1; i <= top1; ++i) {
		top2 = 0;
		for (int j = head[sta1[i]]; j; j = nxt[j]) {
			if (dgr[pnt[j]] == 2) {
				if (tag[pnt[j]]) ans += 2; //两个一级顶点指向一个二级顶点
				else tag[pnt[j]] = 1;
			}
			if (--dgr[pnt[j]] == 0) sta2[++top2] = pnt[j];
		}
		ans += 1LL * top2 * (top2 - 1); //一个一级顶点指向两个二级顶点
		ans += 3LL * top2 * (top1 - 1); //两个一级顶点, 一个二级顶点, 其中二级顶点的入度为1
		for (int i = 1; i <= top2; ++i) //一个一级顶点, 一个二级顶点, 一个三级顶点
			for (int j = head[sta2[i]]; j; j = nxt[j])
				if (dgr[pnt[j]] == 1) ++ans;
		for (int j = head[sta1[i]]; j; j = nxt[j])
			++dgr[pnt[j]]; //恢复度数
	}
	printf("%lld\n", ans);
	return 0;
}

时间复杂度 $O(m \log m)$