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 }
路径压缩
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 5 void ini(vector<int>parents,vector<int>&rank) { 6 for (int i = 0; i < rank.size(); i++) { 7 parents[i] = -1; 8 rank[i] = 0; 9 } 10 } 11 12 int findParent(vector<int>parents, int i) { 13 int root = i; 14 while (parents[root] != -1) { 15 root = parents[root]; 16 } 17 return root; 18 } 19 20 int unionPath(int i, int j, vector<int>parents, vector<int>rank) { 21 int root1 = findParent(parents, i); 22 int root2 = findParent(parents, j); 23 if (root1 == root2) { return 0; } 24 else { 25 if (rank[root1] > rank[root2]) { 26 parents[root2] = root1; 27 } 28 else if(rank[root1]<rank[root2]){ 29 parents[root1] = root2; 30 } 31 else { 32 parents[root1] = root2; 33 rank[root2]++; 34 } 35 return 1; 36 } 37 } 38 39 int main() { 40 int n = 0; 41 cin >> n; 42 43 vector<vector<int>>matrix(n, vector<int>(n, 0)); 44 for (int i = 0; i < n; ++i) { 45 for (int j = 0; j < n; j++) { 46 cin >> matrix[i][j]; 47 } 48 } 49 vector<int>rank(n, 0); 50 vector<int>parents(n,0); 51 ini(parents,rank); 52 53 for (int i = 0; i < n; ++i) { 54 for (int j = i + 1; j < n; ++j) { 55 if (matrix[i][j]) { 56 int b = unionPath(i, j,parents, rank); 57 if (b == 0) { 58 cout << "Loop" << endl; 59 return 0; 60 } 61 } 62 } 63 } 64 cout << "No Loop"; 65 return 0; 66 }