Medium

Number of Connected Components in an Undirected Graph

You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [ai, bi]` indicates that there is an edge between `ai` and `bi` in the graph. Return the number of connected components in the graph.

Examples

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

Output:2

Nodes 0, 1, and 2 form one component. Nodes 3 and 4 form another component. So there are 2 connected components.

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

Output:1

All nodes are connected in a single component.

Constraints

1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
There are no repeated edges.

Union Find

Approach

1. Intuition: We start with `n` nodes, which means initially there are `n` disconnected components. 2. We can use the Union-Find algorithm to merge components as we iterate through the edges. 3. We initialize a `parent` array where each node is its own parent, and a `rank` array to keep the trees balanced. We also keep a `components` counter initialized to `n`. 4. For each edge `(u, v)`, we attempt to union their sets by finding their root parents. 5. If `u` and `v` have different root parents, they belong to different components. We merge these components using union by rank and decrement our `components` counter by 1. 6. If they have the same root parent, they are already in the same component, so we do nothing. 7. After processing all edges, the `components` counter will hold the final number of connected components.

Complexity Analysis

Time Complexity

O(V + E * α(V))

Space Complexity

O(V)

Time complexity is nearly O(V + E) as the union find operations take almost constant time. Space complexity is O(V) for the parent and rank arrays.

Solution.java

1class Solution {2    public int countComponents(int n, int[][] edges) {3        int[] parent = new int[n];4        int[] rank = new int[n];5        6        for (int i = 0; i < n; i++) {7            parent[i] = i;8            rank[i] = 1;9        }10        11        int components = n;12        13        for (int[] edge : edges) {14            if (union(parent, rank, edge[0], edge[1])) {15                components--;16            }17        }18        19        return components;20    }21    22    private int find(int[] parent, int n) {23        if (parent[n] != n) {24            parent[n] = find(parent, parent[n]);25        }26        return parent[n];27    }28    29    private boolean union(int[] parent, int[] rank, int n1, int n2) {30        int p1 = find(parent, n1);31        int p2 = find(parent, n2);32        33        if (p1 == p2) {34            return false;35        }36        37        if (rank[p1] > rank[p2]) {38            parent[p2] = p1;39            rank[p1] += rank[p2];40        } else {41            parent[p1] = p2;42            rank[p2] += rank[p1];43        }44        45        return true;46    }47}