-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathunionFindUndirectedGraph.cpp
More file actions
89 lines (70 loc) · 1.8 KB
/
unionFindUndirectedGraph.cpp
File metadata and controls
89 lines (70 loc) · 1.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
//A structure to represent an edge in graph
class Edge{
public:
int src,dest;
};
//a structure to represent a graph
class Graph{
public:
int V,E;
Edge *edge;
};
//create a graph with V vertices and E edges
Graph *createGraph(int V,int E){
Graph *graph = new Graph();
graph->V = V;
graph->E = E;
graph->edge = new Edge[graph->E * sizeof(Edge)];
return graph;
}
//A utility function to find the subset of an element i
int find(int parent[], int i){
if(parent[i]==-1)
return i;
return find(parent,parent[i]);
}
//A utility funtion to do the union of two set
void Union(int parent[],int x,int y){
int xset = find(parent,x);
int yset = find(parent,y);
if(xset != yset){
parent[xset] = yset;
}
}
//The main function to check whether a graph is having a cycle or not
int isCycle(Graph *graph){
//Allocating memory for creating V subsets
int *parent = new int[graph->V * sizeof(int)];
//Initialize all subsets as single element sets
memset(parent,-1,sizeof(int)*graph->V);
//iterate through all edges of graph, find subset of both vertices of every edge, if both subset are same, then there is a cycle in graph
for(int i = 0; i<graph->E; i++){
int x = find(parent,graph->edge[i].src);
int y = find(parent,graph->edge[i].dest);
if(x==y)
return 1;
Union(parent,x,y);
}
return 0;
}
int main(){
int V=3,E=3;
Graph *graph = createGraph(V,E);
//add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
//add edge 1-2
graph->edge[1].src = 1;
graph->edge[1].dest = 2;
//add edge 0-2
graph->edge[2].src = 0;
graph->edge[2].dest = 2;
if(isCycle(graph)){
cout<<"graph contains cycle";
}else{
cout<<"graph doesn't contains cycle";
}
return 0;
}