本文共 1519 字，大约阅读时间需要 5 分钟。

题目描述

给定一张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 
   
    using namespace std;const int maxn = 30000 + 5;int in[maxn],n,m;vector
    
      G[maxn];vector
     
       topop; //存放拓扑排序后的顺序bitset<30005> bit[maxn];void Topo_sort(){    //拓扑排序    queue
      
        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;}