无向图判环（DFS与并查集）

ps：一道本校院赛题，最后一小时应该开这道题的，导致到比赛结束这道题都看都没看

XP的校园漫步

题目描述

众所周知，XP学长即将毕业了，所以他觉得在校园里来一次漫步，在学校中有N个标志性的建筑，XP学长并不喜欢走小路，因此他会随机的选择某条大路从某个建筑走到另一个建筑，XP学长当然想要走遍校园内的所有建筑，但他会随机的选择某一条路去漫步，当然XP学长走完某一条路，绝对不会走这一条路，也就是说，如果XP学长当前所在建筑为v，他选择走v->u的某一条大路e，到达u建筑后，他在之后的漫步里不会再选择这条路，但是这仍然可能导致他到达某个建筑两次，XP学长表示他不想观看同样的建筑两次，因此他想问问你，如果他随机的选择这些路去漫步，是否会出现到达一个建筑两次或两次以上的现象，当然了，XP学长可以选择任意的建筑作为他的起始点。

输入

输入包含多组测试用例，第一行输入一个T表示测试数据组数，(1<=T<=10)，每组测试数据首先输入有两个整数N，M，N表示校园内有N个建筑(分别用1-N来标记它们)，M表示校园内有M条大路，它们连接着这些建筑。(2<=N<=10^5,1<=M<=105)，接下来M行每行两个整数u，v，表示u，v之间有一条大路(1<=u,v<=N)，每条大路都是无向的，保证图中不出现自环现象，不保证图是连通的。

输出

如果XP学长随机漫步，会出现上述现象，请输出YES，否则输出NO。

样例输入

1
4 3
1 2
2 3
1 3

样例输出

YES

提示
在样例中，XP学长可以选择1作为他的起始建筑，那么他可能走这样的一条路径:1->2->3->1，此时XP学长到达了建筑1两次，因此你需要输出YES。

题意还是很简单，就是判断无向图是否存在环！！

一、DFS：

深度优先遍历时，若存在已经访问过的结点（在正在访问的子图中）则表示有环存在

#include<bits/stdc++.h> using namespace std; int vis[100010]; //判断是否已经访问过 vector<int>mp[100010]; //类似于邻接链表 int dfs(int u,int pre) //u表示当前访问的结点，pre为它的前驱 { int len=mp[u].size(); for(int i=0; i<len; i++) { int v=mp[u][i]; if(v==pre) continue; if(vis[u]==0) { vis[u]=1; if(dfs(v,u)) return 1; //存在环 } else return 1; //存在环 } return 0; } int main() { int t; scanf("%d",&t); while(t--) { memset(mp,0,sizeof(mp)); int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); mp[u].push_back(v); //邻接点 mp[v].push_back(u); //同上 } int flag=0; for(int i=1; i<=n; i++) { if(vis[i]==0) { vis[i]=1; if(dfs(i,0)) { flag=1; break; } } } if(flag==1) printf("YES\n"); //表示存在环 else printf("NO\n"); //表示不存在环 } } 

二、并查集：

若出现一条边的邻接点在同一个集合里，则可证明有环存在

#include<bits/stdc++.h> using namespace std; int par[100010]; //该结点的父亲 int get_par(int a) //找该结点的父亲 { if(par[a]!=a) par[a]=get_par(par[a]); return par[a]; } int Merge(int u,int v) //合并 { int par_u=get_par(u); int par_v=get_par(v); if(par_u==par_v) return 0; //表示在同一集合里面 par[par_v]=par_u; return 1; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) par[i]=i; //初始化 int flag=0; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); if(Merge(u,v)==0) //u，v在同一集合里面 { flag=1; //有环存在 } } if(flag==1) printf("YES\n"); else printf("NO\n"); } return 0; }