DSA-CP-/Disjoint_Set.cpp at main · jatin-code21/DSA-CP- · 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

class DisjointSet
{
    vector<int> rank, parent, size;

public:
    DisjointSet(int n)
    {
        rank.resize(n + 1, 0); // rank is the height of the tree
        parent.resize(n + 1);  // using the one based indexing
        size.resize(n + 1, 1); // size is the number of nodes in the tree
        for (int i = 0; i <= n; i++)
        {
            parent[i] = i;
        }
    }

    int findUltiParent(int node)
    {
        if (node == parent[node])
        {
            return node;
        }
        return parent[node] = findUltiParent(parent[node]);
        // this is the path compression
    }

    void unionByRank(int u, int v)
    {
        int ulp_u = findUltiParent(u);
        int ulp_v = findUltiParent(v);
        if (ulp_u == ulp_v)
        {
            return;
        }
        if (rank[ulp_u] < rank[ulp_v])
        {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u])
        {
            parent[ulp_v] = ulp_u;
        }
        else
        {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void unionBySize(int u, int v)
    {
        int ulp_u = findUltiParent(u);
        int ulp_v = findUltiParent(v);
        if (ulp_u == ulp_v)
        {
            return;
        }
        if (size[ulp_u] < size[ulp_v])
        {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else
        {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt",
            "r", stdin);
    freopen("output.txt",
            "w", stdout);
#endif
    DisjointSet ds(7);
    ds.unionByRank(1, 2);
    ds.unionByRank(2, 3);
    ds.unionByRank(4, 5);
    ds.unionByRank(6, 7);
    ds.unionByRank(5, 6);
    // If 3 and 7 are in same component or not
    if (ds.findUltiParent(3) == ds.findUltiParent(7))
    {
        cout << "Same\n";
    }
    else
    {
        cout << "Not Same\n";
    }
    ds.unionByRank(3, 7);
    // After connecting 3 and 7
    if (ds.findUltiParent(3) == ds.findUltiParent(7))
    {
        cout << "Same\n";
    }
    else
    {
        cout << "Not Same\n";
    }
}