NC51011可达性统计

题目

题目描述

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

输入描述

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

输出描述

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

解析

题目所要求的每个点可以到达的点的数目。其实也就是统计 当前点所指向的点的数目 + 所指向的点的可以到达的点的数目 + 1
这一步很明显是一个递推的过程，所以我们需要找到最低层的点，然后一步一步往前推。
因为这是一个有向无环图，考虑使用拓扑排序，来确定一个合理的从后往前遍历顺序，然后从最低层开始统计。
这里统计数量，我们利用stl的bitset。

bit[v][v] = 1;
for (int j = 0;j < G[v].size();j ++){
    bit[v] = bit[v] | bit[G[v][j]];
}

AC代码：

include <bits/stdc++.h>
using namespace std;

const int maxn = 30000 + 5;
int in[maxn],n,m;
vector<int> G[maxn];
vector<int> topop; //存放拓扑排序后的顺序
bitset<30005> bit[maxn];

void Topo_sort(){ //拓扑排序
    queue<int> que;
    for (int i = 1;i <= n;i ++){
        if (in[i] == 0) que.push(i);
    }
    while (!que.empty()){
        int top = que.front();
        topop.push_back(top);
        que.pop();
        for (int i = 0;i < G[top].size();i ++){
            in[G[top][i]] --;
            if (in[G[top][i]] == 0) que.push(G[top][i]);
        }
    }
}

//反向统计每个顶点可达的顶点数量
void Count(){
    int len = topop.size();
    for (int i = len - 1;i >= 0;i --){
        int v = topop[i];
        bit[v].reset();
        bit[v][v] = 1; //本身可达
        for (int j = 0;j < G[v].size();j ++){
            bit[v] = bit[v] | bit[G[v][j]];
        }
    }
    for (int i = 1;i <= n;i ++){
        cout << bit[i].count() << endl;
    }
}

int main(){
    cin >> n >> m;
    while (m -- ){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        in[v] ++;
    }
    Topo_sort();
    Count();
    return 0;
}