fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define SIZE 10000
  5. int parent[SIZE+1];
  6.  
  7. int Find(int node) {
  8. 	if(parent[node] != node) {
  9. 		parent[node] = Find(parent[node]);
  10. 	}
  11. 	return parent[node];
  12. }
  13.  
  14. void Union(int a, int b) {
  15. 	int parent1, parent2;
  16. 	parent1 = Find(a);
  17. 	parent2 = Find(b);
  18. 	if(parent1 != parent2)
  19. 		parent[parent1] = parent2;	
  20. 	//or parent[parent2] = parent1
  21. }
  22.  
  23. // here a and b can be two end points of the current edge
  24. bool checkCycle(int a, int b) {
  25. 	int parent1, parent2;
  26. 	parent1 = Find(a);
  27. 	parent2 = Find(b);
  28. 	if(parent1 == parent2)
  29. 		return true;
  30. 	return false;
  31. }
  32.  
  33. int main() {
  34.  
  35. 	for(int i=1;i<=SIZE;i++) {
  36. 		parent[i] = i;
  37. 	}
  38.  
  39. 	int m;
  40. 	// assuming m is no of edges and no of nodes is < SIZE
  41. 	cin>>m;
  42.  
  43. 	bool hasCycle = false;
  44. 	for(int i=0;i<m;i++) {
  45. 		int u,v;
  46. 		cin>>u>>v;
  47.  
  48. 		if(!checkCycle(u, v)) {
  49. 			Union(u, v);
  50. 			// graph[u].pb(v);
  51. 			// graph[v].pb(u);
  52. 		}
  53. 		else {
  54. 			hasCycle = true;
  55. 			break;
  56. 		}
  57. 	}
  58.  
  59. 	if(hasCycle) {
  60. 		cout<<"Graph has cycle";
  61. 	}
  62. 	else {
  63. 		cout<<"Graph doesn't have cycle";
  64. 	}
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 16096KB
comments (?)
stdin
copy 
5
1 2
1 3
2 4
2 5
3 5
stdout
copy 
Graph has cycle
https://ideone.com/k0siW9
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!