leetcode-solution/Python/2685-count-the-number-of-complete-components.py at main · hogan-tech/leetcode-solution · 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
# time complexity: O(n + m*a(n))
# space complexity: O(n)
from collections import defaultdict
from typing import List


class UnionFind:
    def __init__(self, size):
        self.parents = [-1] * size
        self.size = [1] * size

    def find(self, node):
        if self.parents[node] == -1:
            return node
        self.parents[node] = self.find(self.parents[node])
        return self.parents[node]

    def union(self, x, y):
        parentX = self.find(x)
        parentY = self.find(y)

        if parentX == parentY:
            return

        if self.size[parentX] > self.size[parentY]:
            self.parents[parentY] = parentX
            self.size[parentX] += self.size[parentY]
        else:
            self.parents[parentX] = parentY
            self.size[parentY] += self.size[parentX]


class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        edgeCount = defaultdict(int)
        for x, y in edges:
            uf.union(x, y)

        for x, _ in edges:
            root = uf.find(x)
            edgeCount[root] += 1

        completeCount = 0
        for vertex in range(n):
            if uf.find(vertex) == vertex:
                nodeCount = uf.size[vertex]
                expectedEdges = (nodeCount * (nodeCount - 1)) // 2
                if edgeCount[vertex] == expectedEdges:
                    completeCount += 1

        return completeCount


n = 6
edges = [[0, 1], [0, 2], [1, 2], [3, 4]]
print(Solution().countCompleteComponents(n, edges))
n = 6
edges = [[0, 1], [0, 2], [1, 2], [3, 4], [3, 5]]
print(Solution().countCompleteComponents(n, edges))