Data-Structures-and-Algorithms/Graphs/07_number_of_connected_components.py at master · Mohammedvaraliya/Data-Structures-and-Algorithms · 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
class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        par = [i for i in range(n)]
        rank = [1] * n

        def find(n):
            res = n

            while res != par[res]:
                par[res] = par[par[res]]
                res = par[res]

            return res

        def union(n1, n2):
            p1, p2 = find(n = n1), find(n = n2)

            if p1 == p2:
                return 0

            if rank[p2] > rank[p1]:
                par[p1] = p2
                rank[p2] += rank[p1]
            else:
                par[p2] = p1
                rank[p1] += rank[p2]

            return 1

        res = n
        for n1, n2 in edges:
            res -= union(n1 = n1, n2 = n2)

        return res


if __name__ == "__main__":

    obj = Solution()

    n1 = 3
    edges1 = [[0,1], [0,2]]
    print(obj.countComponents(n = n1, edges = edges1))

    n2 = 6
    edges2 = [[0,1], [1,2], [2, 3], [4, 5]]
    print(obj.countComponents(n = n2, edges = edges2))