0323 Number of Connected Component in an Undirected Graph

0323 Number of Connected Component in an Undirected Graph#

Problem#

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Examples#

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Analysis#

  • This is a typical problem that can be solved using union-find algorithm.

  • This is also solvable using DFS/BFS method, as in number of islands problems.

Solution#

DFS#

def numberOfConnectedComponents(n, edges):
    # 1. construct graph
    graph = {}
    for i in range(n):
        graph[i] = []
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    # 2. dfs
    visited = set()
    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
    # 3. count
    count = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    return count

# test
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(numberOfConnectedComponents(n, edges))

n = 5
edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
print(numberOfConnectedComponents(n, edges))

2
1

BFS#

def numberOfConnectedComponents(n, edges):
    # 1. construct graph
    graph = {}
    for i in range(n):
        graph[i] = []
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    # 2. bfs
    visited = set()
    def bfs(graph, node):
        queue = [node]
        while queue:
            node = queue.pop(0)
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    # 3. count
    count = 0
    for i in range(n):
        if i not in visited:
            bfs(graph, i)
            count += 1
    return count

# test
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(numberOfConnectedComponents(n, edges))

n = 5
edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
print(numberOfConnectedComponents(n, edges))

2
1

Union-Find#

class UnionFind():
    def __init__(self, n):
        # set parent for each node as itself
        self.parent = [i for i in range(n)]
        # set count as n
        self.count = n

    def find(self, node):
        # find root for node, and compress path. This makes the find time complexity O(1)
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    
    def union(self, node1, node2):
        # find root for node1 and node2
        root1 = self.find(node1)
        root2 = self.find(node2)
        # if root1 != root2, union them
        if root1 != root2:
            self.parent[root1] = root2
            self.count -= 1
    def count(self):
        return self.count

def numberOfConnectedComponents(n, edges):
    # 1. construct union find
    uf = UnionFind(n)
    # 2. union
    for edge in edges:
        uf.union(edge[0], edge[1])
    # 3. return count
    return uf.count

# test
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(numberOfConnectedComponents(n, edges))

n = 5
edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
print(numberOfConnectedComponents(n, edges))

2
1
Contents