Yuzhen's Blog

Yuzhen Qin

题解:P10480 可达性统计

7
2024-06-17

题意

给定一张 N 个点 M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量1\le N,M\le 30,000

做法

对于每一个点进行 DFS 搜索。使用 std::bitset 记录能够到达的点。当搜索到一个点时,如果已经被搜索过,直接按位或该点能够到达的点的 bitset。最终使用 bitset::count() 统计能够到达的点。

完整代码

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

bitset<30001> f[30001];
vector<int> e[30001];
bool vis[30001];

void dfs(int u) {
	if(vis[u]) return;
	vis[u] = true;
	
	for(int v : e[u]) {
		dfs(v);
		f[u] |= f[v];
	}
}

int main(void) {
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		f[i][i] = 1;
		
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y); 
	}
	
	for(int i = 1; i <= n; i++) {
		dfs(i);
		cout << f[i].count() << endl; 
	}
	
	return 0;
}