LeetCode - Number of Connected Components in an Undirected Graph

NumberofConnectedComponentsinanUndirectedGraph.java

// 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.

// Example 1:
//     0          3
//     |          |
//     1 --- 2    4
// Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

// Example 2:
//     0           4
//     |           |
//     1 --- 2 --- 3
// Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

// Note:
// 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.

public int countComponents(int n, int[][] edges) {
    if(n <= 0) return 0;
    int[] parents = new int[n];
    Arrays.fill(parents, -1);
    
    for(int i = 0; i < edges.length; i++){
        union(parents, edges[i][0], edges[i][1]);
    }
    
    int count = 0;
    for(int i = 0; i < n; i++){
        if(parents[i] == -1) count++;
    }
    
    return count; 
}

private int find(int[] parents, int i){
    if(parents[i] != -1) 
        return find(parents, parents[i]);
    return i;
}

private void union(int[] parents, int i, int j){
    int parent_i = find(parents, i);
    int parent_j = find(parents, j);
    if(parent_i != parent_j)
        parents[parent_i] = parent_j;
}


// BFS, DFS and https://leetcode.com/discuss/76753/easiest-2ms-java-solution