请教为什么不反向建边会WA?
查看原帖
请教为什么不反向建边会WA?
1051584
Crushxl楼主2024/5/27 19:53

如题,初学图论不是很明白为什么要这么做

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e3+5;
int k,n,m,u,v,ans;
vector<int> g[MAXN];
unordered_set<int> conn[MAXN];
unordered_set<int> pos;

void dfs(int x,int root){
	conn[root].insert(x);
	for(int i=0;i<g[x].size();i++){
		int y = g[x][i];
		if(conn[root].find(y) == conn[root].end()){
			dfs(y,root);
			conn[root].insert(y);
		}
	}
}

bool judge(int id){
	for(auto it=pos.begin();it!=pos.end();it++){
		int now = *it;
		if(conn[id].find(now) == conn[id].end()){
			return false;
		}
	}
	return true;
}

int main(){
	cin >> k >> n >> m;
	for(int i=1;i<=k;i++){
		cin >> u;
		pos.insert(u);
	}
	for(int i=1;i<=m;i++){
		cin >> u >> v;
		g[v].push_back(u);	//反向建边
	}
	for(int i=1;i<=n;i++){
		dfs(i,i);
	}
	for(int i=1;i<=n;i++){
		if(judge(i)){
			ans++;
		}
	}
	cout << ans;
	return 0;
}
2024/5/27 19:53
加载中...