「拓扑排序」可达性统计
2020-12-13 14:05
阅读：485
标签：相关 push sort 理论 class scanf while 拓扑 href
可达性统计
原题链接：可达性统计
题目大意
给你一张\(n\)个点\(m\)条边的有向无环图，分别统计从每个点出发能够到达的点的数量
题目题解
看到题意就知道要用到拓扑排序，但是拓扑排序的理论复杂度在30000的极限条件下会超时，这个时候我们考虑使用 \(bitset\)，一个很好用的代替bool的防卡常技巧，详细的说明这里不说，可以去百度上查看相关运用
//#define fre yes
#include
#include
#include
#include
#include
const int N = 30005;
int head[N f[N];
int tot, k;
void addedge(int x, int y) {
ver[tot] = y;
to[tot] = head[x];
head[x] = tot++;
}
int n, m;
void toposort() {
std::queue q;
for (int i = 1; i = 1; i--) {
int j = ans[i];
f[j][j] = 1;
for (int x = head[j]; ~x; x = to[x]) {
f[j] |= f[ver[x]];
}
}
for (int i = 1; i 「拓扑排序」可达性统计
标签：相关 push sort 理论 class scanf while 拓扑 href
原文地址：https://www.cnblogs.com/Nicoppa/p/11549865.html
评论
亲，登录后才可以留言！