判断一个图中是否有环
问题描述
给一个以0 0结尾的整数对列表，除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图中是否存在环。存在输出YES，不存在输出NO。
输入样例1
6 8 5 3 5 2 6 4 5 6 0 0
输出样例1
NO
输入样例2
8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0
输出样例2
NO
输入样例3
3 8 6 8 6 4 5 3 5 6 5 2 0 0
输出样例3
YES
输入样例4
1 2 3 4 0 0
输出样例4
NO
输入样例5
空图没有环
0 0
输出样例5
NO
c++代码
#include<bits/stdc++.h>using namespace std;int a, b;
int arr[100001];
bool key = false;int myfind(int x) {int root = x;while(root != arr[root]) root = arr[root];int i = x, j;while(i != root) {j = arr[i];arr[i] = root;i = j;}return root;
}void mymerge(int x, int y) {x = myfind(x), y = myfind(y);if (x != y) arr[y] = arr[x];
}int main() {for (int i = 1; i <= 100000; i++) arr[i] = i;while(true) {scanf("%d %d", &a, &b);if (a == 0 && b == 0) break;if (key) continue;int x = myfind(a), y = myfind(b);if (x == y) key = true;else mymerge(a, b);}if (key) printf("YES");else printf("NO");return 0;
}//by wqs
算法解析
给每个点一个初始的编号，并初始化所有节点的父亲为本身。每新加入一条边就把边相连的两个集合合并到一起，如果边相连的集合原本就是同一个，说明已经成环。