hacktoberfest-2022/Disjoint_set.cpp at main · tamanna863/hacktoberfest-2022 · 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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
using namespace std;

/* UnionFind/Disjoint Set data structure implementation */
class UnionFind
{
private:
    int nsize;   // number of nodes in this union find
    int *gs;     // to store size of each group
    int *parent; // points to the parent
    int rsize;   // number of root Nodes in the union find

public:
    UnionFind(int sz, bool def)
    {

        if (def == true)
        {
            nsize = rsize = sz;
            gs = new int[sz];
            parent = new int[sz];
            for (int i = 0; i < nsize; ++i)
            {
                parent[i] = i;
                gs[i] = 1;
            }
        }
        else
        {
            nsize = rsize = 0;
            parent = new int[sz];
            gs = new int[sz];
        }
    }

    void add(int p)
    {
        parent[p] = p;
        gs[p] = 1;
        nsize++;
        rsize++;
    }

    // Find which component/set 'p' belongs to, takes amortized constant time.
    int find(int p)
    {
        int root = p;
        while (root != parent[root])
            root = parent[root];

        // Compress the path leading back to the root.
        // Doing this operation is called "path compression"
        // and is what gives us amortized time complexity.
        while (root != parent[p])
        {
            int next = parent[p];
            parent[p] = root;
            p = next;
        }

        return root;
    }

    bool connected(int p, int q)
    {
        return find(p) == find(q);
    }
    void unify(int p, int q)
    {
        int r1 = find(p);
        int r2 = find(q);

        if (connected(p, q))
            return;

        if (gs[r1] < gs[r2])
        {
            gs[r2] += gs[r1];
            parent[r1] = r2;
            gs[r1] = 0;
        }
        else
        {
            gs[r1] += gs[r2];
            parent[r2] = r1;
            gs[r2] = 0;
        }

        rsize--;
    }

    // Return the size of the group/node 'p' belongs to
    int componentSize(int p)
    {
        return gs[find(p)];
    }

    int size()
    {
        return nsize;
    }

    int components()
    {
        return rsize;
    }
};

int main()
{
    UnionFind gg(5, true);
    // gg.add(10);
    // gg.add(20);
    // gg.add(30);
    // gg.add(60);
    // gg.add(80);
    // gg.unify(10,20);
    gg.unify(0, 3);
    gg.unify(0, 1);
    gg.unify(2, 4);
    gg.unify(2, 3);
    // cout << gg.find(10) << '\n';
    // cout << gg.find(20) << '\n';
    // cout << gg.find(30) << '\n';
    // cout << gg.find(60) << '\n';
    // cout << gg.find(80) << '\n';

    cout << gg.find(0) << '\n';
    cout << gg.find(1) << '\n';
    cout << gg.find(2) << '\n';
    cout << gg.find(3) << '\n';
    cout << gg.find(4) << '\n';
    cout << gg.componentSize(3) << '\n';

    // cout << gg.find(5) << '\n';
    // cout << gg.find(6) << '\n';
    // cout << gg.find(7) << '\n';
    // cout << gg.find(3) << '\n';
}