LeetCode #323: Number of Connected Components in an Undirected Graph

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/

This problem can be solved using the Union-Find algorithm. We can use two arrays, par and rank to keep track of the parent and the rank of each node, respectively. Initially, each node will have itself as its parent, and its rank will be set to 1.

We will then define two functions: find and union. The find function will find the root parent of a given node. It will start from the given node and traverse the parent array until it reaches a node whose parent is itself. The function also applies the path compression optimization to reduce the height of the tree.

The union function will union two nodes if they are not already connected. First, it will find the root parents of both nodes using the find function. If both nodes have the same root parent, then they are already connected, and we can return 0. Otherwise, we will compare the ranks of the root parents and connect the smaller rank tree to the larger rank tree. Finally, we will update the rank of the larger rank tree to be the sum of the ranks of both trees.

We can iterate through the list of edges and call the union function on each pair of nodes. Each time a new union is made, we will decrement the count of the number of components. The final answer will be the count of the number of remaining nodes.

1. Initialize par and rank arrays where each node has itself as its parent and a rank of 1.
2. Define the find function that will find the root parent of a given node using path compression optimization.
3. Define the union function that will union two nodes if they are not already connected. It will use the find function to find the root parents of the nodes and connect the smaller rank tree to the larger rank tree. It will also update the rank of the larger rank tree.
4. Iterate through the list of edges and call the union function on each pair of nodes. Decrement the count of the number of components each time a new union is made.
5. Return the count of the number of remaining nodes.

Here is the solution in python3:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        par = [i for i in range(n)]
        rank = [1] * n
        def find(n1):
            res = n1
            while res != par[res]:
                par[res] = par[par[res]]
                res = par[res]
            return res
        def union(n1, n2):
            p1, p2 = find(n1), find(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
        for n1, n2 in edges:
            n -= union(n1, n2)
        return n

Time Complexity

The time complexity of both DFS and BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. In the worst case, we would need to visit every vertex and every edge in the graph.

Space Complexity

The space complexity of both DFS and BFS is O(V), where V is the number of vertices in the graph. This is because we need to maintain a visited set and a queue or stack for the traversal, both of which can have at most V elements.