AcWing 164 可达性统计 (拓扑排序 + bitset)

题目链接：https://www.acwing.com/problem/content/description/166/

拓扑排序：
对于图中每条边((x,y)), 如果在序列(A)中，(x) 始终出现在 (y) 的前面，则称序列 (A) 为该图的拓扑序

用 (bfs) 求解拓扑序，首先让所有入度为 (0) 的点入队，然后每次取出队首节点，加入拓扑序，
遍历该节点的出边，出边节点入读减一，如果减一后入度变为 (0),则将此出边节点入队

bitset:
需要头文件:
#include<bitset>
支持集合操作，复杂度为 (frac{理论复杂度}{32})
初始化：

bit.size()       返回大小（位数）
bit.count()     返回1的个数
bit.any()       返回是否有1
bit.none()      返回是否没有1
bit.set()       全都变成1
bit.set(p)      将第p + 1位变成1（bitset是从第0位开始的！） 
bit.set(p, x)   将第p + 1位变成x
bit.reset()     全都变成0
bit.reset(p)    将第p + 1位变成0
bit.flip()      全都取反
bit.flip(p)     将第p + 1位取反
bit.to_ulong()  返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string() 返回它转换为string的结果

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;

const int maxn = 30010;

int n, m, tot;

bitset<maxn> f[maxn];

queue<int> q;

int h[maxn], d[maxn], tp[maxn], cnt = 0;

struct E{
	int to, next;
}e[maxn<<1];

void add(int u, int v){
	e[++cnt].next = h[u];
	e[cnt].to = v;
	h[u] = cnt;
} 

void topsort(){
	for(int i=1;i<=n;++i){
		if(!d[i]) q.push(i);
	}
	
	while(!q.empty()){
		int u = q.front(); q.pop();
		tp[++tot] = u;
		for(int i=h[u];i!=-1;i=e[i].next){
			int v = e[i].to;
			if(--d[v] == 0) q.push(v);
		}
	}
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	memset(h, -1, sizeof(h));
	n = read() ,m = read(); tot = 0;
	
	int u, v;
	for(int i=1;i<=m;++i){
		u = read(), v = read();
		++d[v];
		add(u, v); 
	} 
	
	topsort();
	
	for(int i=n;i>=1;--i){
		u = tp[i];
		f[u][u] = 1;
		for(int j=h[u];j!=-1;j=e[j].next){
			v = e[j].to;
			f[u] |= f[v];
		}
	}
	
	for(int i=1;i<=n;++i) cout << f[i].count() << endl;
	
	return 0;
}