并查集， 判断是否存在环

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 //n-节点数
 5 //m-边的数
 6 //给一幅图，判断是否存在环
 7 int find_root(int x, vector<int>&parent) {
 8     if (parent[x] == -1) {
 9         return x;
10     }
11     int root = find_root(parent[x], parent);
12     return root;
13 }
14 
15 int main(){
16     int n, m;
17     cin >> n, m;
18     vector<int>parent(n,-1);
19     for (int i = 1; i < m; ++i) {
20         int x, y;
21         cin >> x >> y;
22         //连通，且又存在一条相连的边
23         if (find_root(x, parent) == find_root(y, parent)) {
24             cout << "cycle found" << endl;
25         }
26         else {
27             parent[find_root(x,parent)] = find_root(y, parent);
28         }
29     }
30     cout << "no cycle" << endl;
31     return 0;
32 }