Kosaraju20分求助
查看原帖
Kosaraju20分求助
476720
_pharos_C楼主2023/6/3 11:41
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n, a, cnt, m;
int id[maxn];
bool vis[maxn];
vector<int> G[maxn], G1[maxn], sta;

void dfs_o(int u) {
	if(vis[u]) 
		return;
	vis[u] = 1;
	for(int v=0; v<G[u].size(); v++) 
		if(!vis[G[u][v]]) 
			dfs_o(G[u][v]);
	sta.push_back(u);
}

int num;
void dfs(int u) {
	if(id[u]) return;
	id[u] = num;
	for(int i=0; i<G1[u].size(); i++) {
		dfs(G1[u][i]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i=1, a, b; i<=m; i++) {
		cin >> a >> b;
			G[a].push_back(b);
			G1[b].push_back(a);
	}
	for(int i=1; i<=n; i++)
		dfs_o(i);
	for(int i=n - 1; i>=0; i--) {
		if(!id[sta[i]]) {
			num++;
			dfs(sta[i]);
		}
	}
	cout << num << endl;
	return 0;
}
2023/6/3 11:41
加载中...