「拓扑排序」可达性统计

2020-12-13 14:05

阅读：469

标签：相关 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

上一篇：Unity3D 中的灯光与渲染

下一篇：有关windows服务的问题（转载自http://www.itjie.wang/）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「拓扑排序」可达性统计
文章链接：http://soscw.com/essay/33675.html

亲，登录后才可以留言！

「拓扑排序」可达性统计

可达性统计

题目大意

题目题解

评论

热门文章

推荐文章

最新文章

置顶文章