AcWing 164. 可达性统计

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 164. 可达性统计原题链接中等

作者：

Bug-Free , 2021-01-26 23:39:06 , 所有人可见 , 阅读 6205

64

28

代码

/*
 * Project: 0x21_树与图的遍历
 * File Created:Tuesday, January 26th 2021, 7:31:09 pm
 * Author: Bug-Free
 * Problem:Acwing 164. 可达性统计
 */
#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 3e4 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], seq[N];  //入度， 拓扑序列

bitset<N> f[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// 只有有向无环图， 才能做拓扑排序
// 拓扑排序
void topsort() {
    queue<int> q;

    // 先把所有入度为 0 的点加入队列（有向图）
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            q.push(i);
        }
    }
    // k表示当前拓扑排序中元素的个数
    int k = 0;
    while (q.size()) {
        int t = q.front();
        q.pop();
        seq[k++] = t;  //将队头元素加入拓扑序中
        //将当前点可以到的点的入度--（删去x连向其他点的边）
        for (int i = h[t]; ~i; i = ne[i]) {  // 遍历这个点所有的邻边
            int j = e[i];  // e[i] 表示 邻边所对应的终点
            if (--d[j] ==
                0) {  //如果j这个点的入度为0了，那我们就可以加到队列中去
                q.push(j);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;  //有一条 a 指向 b的边， 因此b的入度+1
    }

    topsort();

    // 从后往前递推
    // bitset<N> s;
    // s[k] 表示 第k位， 既可以取值， 也可以赋值
    for (int i = n - 1; i >= 0; i--) {
        int j = seq[i];
        f[j][j] = 1;  // j这个点可以到达自己   f[j][j] =表示从 j出发的点，
                      // 能够到的点（1表示可以到， 0表示不能到），j可以到自己，
                      // 因此f[j][j]=1
        for (int k = h[j]; ~k; k = ne[k]) {  //所有能到到达的点
            f[j] |= f[e[k]];  // j这个点可以到达的点的数量= {j} U {y1} U {y2}
                              // ... {yn}
        }
    }
    for (int i = 1; i <= n; i++) {
        // f[i].count() 返回f[i] 中 1的个数
        cout << f[i].count() << endl;
    }
    return 0;
}

15 评论

祁连飞鱼 2022-12-10 20:23

//可以直接倒序遍历
#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
const int N = 30010,M = 30010;
int n,m,idx,h[N],e[M],ne[M],q[N],din[N];
bitset<N> w[N];
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void topsort(){
    int hh = 0,tt = -1;
    for(int i = 1;i <= n;++i)
        if(!din[i]) q[++tt] = i;
    for(int i = 1;i <= n;++i) w[i][i] = 1;//本身可达
    while(hh <= tt){
        int t = q[hh++];
        //w[t][t] = 1;//err:丢出来就已经确定了，不能重置
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            w[j] |= w[t];
            if(--din[j] == 0) q[++tt] = j;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(b,a);
        ++din[a];
    }
    topsort();
    for(int i = 1;i <= n;++i) printf("%d\n",w[i].count());
    return 0;
}

懒惰的蚩蚩 5个月前

你跟我想的一模一样，我前面奖金那题也用了倒序，一下子就做出来了，但是这题我想到了倒序，唯一一点就是不知道这个bitset，然后没做出来

懒惰的蚩蚩 5个月前

你可以在找入度为0的点的时候，顺便将所有点都本身可达初始化w为1，那样可以节省一个循环

ligg 2022-07-21 15:26

f[N]不是一维的吗，为什么可以用f[j][j]

incra 2022-07-29 08:27

$bitset$ 支持询问某一个数的第几位二进制，所以可以用 $f[j][j]$，意思就是第 $j$ 个数的第 $j$ 二进制数是多少（也可以支持修改）

ligg 2022-07-29 10:18 回复了 incra 的评论

感谢大佬~

incra 2022-07-29 10:20 回复了 ligg 的评论

不用蟹~

legola 2023-03-19 18:21

还不会拓扑排序的伙伴们看下这篇博客，感觉讲得很好！

baikun 11个月前

bitnet用的很妙

Banabo 2023-02-14 20:34

我竟然看懂了，果断收藏

蓝鲸 2022-10-11 23:54

%%%%%%%%%%%%%%%%%

shark_big 2022-03-29 19:46

Orz

shark_big 2022-03-29 19:46

Segmentation Fault
求助

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
const int N=30010;
int a,b,n,m,cnt=0,cn=0,head[N],mon[N],so[N];
bitset<N> f[N];
struct node{
    int next,to;
}sb[20005];
void add(int a,int b){
    sb[++cnt].next=head[a],head[a]=cnt,sb[cnt].to=b;
    so[b]++;
} 
void topu(){
    queue<int> s;
    for(int i=1;i<=n;i++)
        if(!so[i]) s.push(i);
    while(s.size()){
        int t=s.front();
        s.pop();
        mon[++cn]=t;
        for(int i=head[t];i;i=sb[i].next){
            int tt=sb[i].to;
            if(--so[tt]==0){
                s.push(tt);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(head,0,sizeof head);
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        add(a,b);
    }
    topu();
    for(int i=1;i<=n;i++){
        int t=mon[n-i+1];
        f[t][t]=1;
        for(int j=head[t];j;j=sb[j].next){
            f[t]|=f[sb[j].to];
        }
    }
    for(int i=1;i<=n;i++)
        cout<<f[i].count()<<endl;
    return 0;
}

Once. 2021-08-19 11:46

写的太细了，对萌新太友好了，棒！

Sora1336 2021-07-30 19:40

写的太好了！兹磁作者qwq

App 内打开

AcWing 164. 可达性统计 原题链接 中等

代码

15 评论

AcWing 164. 可达性统计原题链接中等