323. Number of Connected Components in an Undirected Graph

Description

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.

Constraints

• 1 <= n <= 2000

• 1 <= edges.length <= 5000

• edges[i].length == 2

• 0 <= ai <= bi < n

• ai != bi

• There are no repeated edges.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: 2

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

Output: 1

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        
        for(int i = 0; i < n; i++) {
            root[i] = i;
        }
        
        int count = n;
        for(int[] edge: edges) {
            int xRoot = getRoot(root, edge[0]);
            int yRoot = getRoot(root, edge[1]);
            
            if(xRoot != yRoot) {
                count--;
                root[xRoot] = yRoot;
            }
        }
        
        return count;
    }
    
    private int getRoot(int[] root, int node) {
        while(root[node] != node) {
            root[node] = root[root[node]];
            node = root[node];
        }
        return node;
    }
}

Follow up