LC-0323 Medium LeetCode

323. Number of Connected Components in an Undirected Graph

Depth-First Search Breadth-First Search Union Find Graph

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 64% Topics: Depth-First Search, Breadth-First Search, Union Find, Graph

Reading material

Trees & Traversals 18 min Union–Find (DSU) 12 min Graphs 16 min

Reference solution (spoiler · python)

# Time:  O(nlog*n) ~= O(n), n is the length of the positions
# Space: O(n)

class UnionFind(object):
    def __init__(self, n):
        self.set = range(n)
        self.count = n

    def find_set(self, x):
       if self.set[x] != x:
           self.set[x] = self.find_set(self.set[x])  # path compression.
       return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = map(self.find_set, (x, y))
        if x_root != y_root:
            self.set[min(x_root, y_root)] = max(x_root, y_root)
            self.count -= 1


class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        union_find = UnionFind(n)
        for i, j in edges:
            union_find.union_set(i, j)
        return union_find.count

Solution from kamyu104/LeetCode-Solutions · MIT