【HDU】5222 Exploration（并查集+拓扑排序）

本文主要是介绍【HDU】5222 Exploration（并查集+拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于无向边使用并查集合并成一个集合，对于有向边使用判断是否存在环

唯一无语的地方就是看输入是百万级的，加个输入挂跑9s，不加挂跑了5s

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1000005;
int N,M1,M2,cnt;
int fa[maxn],vis[maxn];
vector<int>G[maxn];
int find_father(int u){return u == fa[u] ? u : fa[u] = find_father(fa[u]);
}
void init(){for(int i = 1; i <= N; i++) fa[i] = i;for(int i = 1; i <= N; i++) G[i].clear();
}
bool dfs(int v){vis[v] = -1;for(int i = 0; i < G[v].size(); i++){int e = G[v][i];if(vis[e] < 0) return false;if(!vis[e] && !dfs(e)) return false;}vis[v] = 1;return true;
}
int solve(){memset(vis,0,sizeof(vis));for(int i = 1; i <= N; i++){int e = find_father(i);if(!vis[e]){if(!dfs(e)) return true;}}return false;
}
int main(){int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&N,&M1,&M2);int u,v,ok = 0;init();getchar();for(int i = 0; i < M1; i++){scanf("%d%d",&u,&v);int f1 = find_father(u);int f2 = find_father(v);if(f1 == f2)ok = 1;elsefa[f1] = f2;}for(int i = 0; i < M2; i++){scanf("%d%d",&u,&v);if(!ok){int f1 = find_father(u);int f2 = find_father(v);G[f1].push_back(f2);}}if(ok)printf("YES\n");else{ok = solve();if(ok)printf("YES\n");elseprintf("NO\n");}}return 0;
}

这篇关于【HDU】5222 Exploration（并查集+拓扑排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---