CH 2101 可达性统计(进阶指南， 位运算，拓扑排序)

算法竞赛进阶指南， 99 页

本题要点：
1、有向无环图，拓扑排序之后，得到拓扑序列 top_order[MaxN]。
top_order[i] 可以到达的点 假设为 f(top_order[i])，等于 top_order[i]所有相邻的点 (假设其中任意一点为j)
可以到达的点f(j)的并集。因此，从后往前扫描拓扑序列，依次求并集。

2、 用c++的 bitset 模板来处理位运算。参考 https://www.cnblogs.com/magisk/p/8809922.html
构造函数 ： bit.set(i), 表示第i位置1;
统计1的个数：bit.count()

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <bitset>
using namespace std;
const int MaxN = 30010;
const int MaxM = 30010;
bitset<MaxN> bit[MaxN];
int top_order[MaxN];
int top_cnt = 0;
int n, m, tot;
int ver[MaxN], head[MaxN], ne[MaxN], deg[MaxN];void add(int x, int y)
{
    ver[++tot] = y, ne[tot] = head[x], head[x] = tot;deg[y]++;
}void topsort()
{
    queue<int> q;for(int i = 1; i <= n; ++i)	//所有点的号码 1 ~ n{
    if(0 == deg[i]){
    q.push(i);}}while(q.size()){
    int x = q.front();q.pop();top_order[top_cnt++] = x;for(int i = head[x]; i; i = ne[i]){
    int y = ver[i];if(--deg[y] == 0){
    q.push(y);}}}
}void solve()
{
    for(int i = 1; i <= n; ++i){
    bit[i].set(i);	}for(int i = top_cnt - 1; i >= 0; --i){
    int x = top_order[i];for(int j = head[x]; j; j = ne[j])	{
    int y = ver[j];	bit[x] |= bit[y];}}for(int i = 1; i <= n; ++i){
    printf("%d\n", (int)(bit[i].count()));}
}int main()
{
    int a, b;scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i){
    scanf("%d%d", &a, &b);add(a, b);}topsort();solve();return 0;
}/* 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 */