【bieset优化】可达性统计

柔情只为你懂 2024-03-25 16:10 13阅读 0赞

还没怎么用过bitset

感觉就是可以快死位运算和统计1的个数的01数组

[164. 可达性统计 - AcWing题库][164. _ - AcWing]

题意：

![f63e03fe876998725519e793bc5082af.png][]

思路：

拓扑排序把拓扑序跑出来

跑出来之后逆着拓扑序把可达的点的集合都或上，然后可以快速求出1的个数

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=3e4+10,mxe=3e4+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    vector<int> v;
    queue<int> q;
    int n,m,x,y,tot=0;
    bitset<mxn> f[mxn];
    int head[mxn],in[mxn],dp[mxn];
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            in[i]=0;
            dp[i]=1;
        }
        while(!q.empty()) q.pop();
    }
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void topsort(){
        for(int i=1;i<=n;i++){
            if(!in[i]) q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            v.push_back(u);
            for(int i=head[u];~i;i=edge[i].next){
                in[edge[i].to]--;
                if(!in[edge[i].to]) q.push(edge[i].to);
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            add(x,y),in[y]++;
        }
        topsort();
        for(int i=v.size()-1;i>=0;i--){
            int u=v[i];
            f[u][u]=1;
            for(int j=head[u];~j;j=edge[j].next){
                f[u]|=f[edge[j].to];
            }
        }
        for(int i=1;i<=n;i++) cout<<f[i].count()<<'\n';
    }

[164. _ - AcWing]: https://www.acwing.com/problem/content/166/
[f63e03fe876998725519e793bc5082af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b6c78c69703545fcbb760fc8022fd8f5.png