CS204/dsu.cpp at master · krtky123/CS204 · GitHub

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
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int src,dest;
};

struct Graph
{
    int V;
    int E;
    struct Edge *edge;

};

struct subset
{
    int parent;
    int rank;
};

struct Graph* createGraph(int V,int E)
{
    struct Graph* graph=(struct Graph*)malloc(sizeof(struct Graph));
    graph->V=V;
    graph->E=E;
    graph->edge=(struct Edge*)malloc(sizeof(struct Edge));
    return graph;

}

int find(struct subset subsets[],int x)
{
    if(subsets[x].parent==x)return x;
    subsets[x].parent=find(subsets,subsets[x].parent);
    return subsets[x].parent;
}

void Union(struct subset subsets[],int x,int y)
{
    int set1=find(subsets,x);
    int set2=find(subsets,y);
    if(subsets[set1].rank>subsets[set2].rank)
    {
        subsets[set2].parent=set1;
    }

    else if(subsets[set1].rank<subsets[set2].rank)
    {
        subsets[set1].parent=set2;
    }
    else
    {
        subsets[set1].parent=set2;
        subsets[set2].rank++;
    }

}

int isCycle(struct Graph* graph)
{
    struct subset subsets[graph->V];
    for(int i=0;i<graph->V;i++)
    {
        subsets[i].parent=i;
        subsets[i].rank=0;
    }
    for(int i =0;i<graph->E;i++)
    {
        int x=find(subsets,graph->edge[i].src);
        int y=find(subsets,graph->edge[i].dest);
        if(x==y)return 1;
        Union(subsets,x,y);
    }
    return 0;
}

int main()
{
    int v=5,e=4;
    struct Graph* graph=createGraph(5,4);
    graph->edge[0]={0,1};
    graph->edge[1]={1,2};
    graph->edge[2]={2,3};
    graph->edge[3]={3,1};
    if(isCycle(graph))cout<<"YES";
    else cout<<"NO";
}