可达性统计

题目

给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数N,M,接下来M行每行两个整数x,y,表示从x到y的一条有向边。

输出格式

输出共N行,表示每个点能够到达的点的数量。

数据范围

1≤N,M≤30000

输入样例:

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

输出样例:

1
6
3
3
2
1
1
1
1
1

分析:

  • 这个题目比较简单,但是数据量大,普通的存图方法会存不下,因此我们要变换思路,直接求结果。
  • 我们可以根据拓扑排序来倒推结果,拓扑排序的最后一个点,把他的值设为1。用bitseet容器存每个点的下一个邻接点,是邻接的那一位即为1,否则为零,1的个数既是答案,将答案进行或操作可以得到上一个点的答案。

代码

#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
const int N=3e4+5;

struct node{
    int to,next; 
}edge[N];
int head[N],idx;
void  addedge(int u,int v){ //链式前向星 
    edge[++idx].to=v;
    edge[idx].next=head[u];
    head[u]=idx;
}

bitset<N> f[N]; //bitset容器 
int du[N],res[N],cnt;  
int n,m;

void topsort(){ // 拓扑排序 
    queue<int> q;
    for(int i=1;i<=n;i++){ // 将度为零的点加入队列 
        if(!du[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front(); // 删除队首元素 
        q.pop();
        res[cnt++]=u;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to; 
            if(--du[v]==0){ // 删除队首元素相邻边 
                q.push(v); // 度为零再加入队列 
            }
        }
    }
}

int main()
{
    int a,b;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        addedge(a,b);
        du[b]++;
    }
    topsort();
    for(int i=cnt;~i;i--){ //根据拓扑排序从后往前推 
        int j=res[i];
        f[j][j]=1;
        for(int k=head[j];k;k=edge[k].next){
            int v=edge[k].to;
            f[j]|=f[v];
        }
    }
    //每个bitset里1的个数就是答案 
    for(int i=1;i<=n;i++) cout<< f[i].count() <<endl;
    return 0;
}

   转载规则


《可达性统计》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录