164. 可达性统计 topsort

// 164. 可达性统计.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/166/

给定一张 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
*/
#include <iostream>
#include <bitset>
#include <queue>

using namespace std;

const int N = 30010;
int h[N], e[N], ne[N], idx;
int n, m;
bitset<N> dp[N];
int din[N], dout[N];
bool vis[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (din[i] == 0) {
			q.push(i);
		}
	}
	vector<int> pv;
	while (q.size()) {
		int t = q.front(); q.pop();
		pv.push_back(t);
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			din[j]--;
			if (din[j] == 0) {
				q.push(j);
			}
		}
	}
}

void dfs(int x) {
	if (vis[x] == true) return;
	vis[x] = true; dp[x].set(x);
	for (int i = h[x]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		dp[x] |= dp[j];
	}
}


int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		add(a, b);
		din[b]++; dout[a]++;
	}

	topsort();

	for (int i = 1; i <= n; i++) {
		dfs(i);
	}

	for (int i = 1; i <= n; i++) {
		cout << dp[i].count() << endl;
	}
}