Leetcode: Number of Connected Components in an Undirected Graph

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.

DFS Solution:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 0 || edges == null) {
            return 0;
        }
        
        if (n == 1 && edges.length == 0) {
            return 1;
        }
        
        int result = 0;
        boolean[] visited = new boolean[n];
        
        // step 1: create the adj list from edge list
        List[] adjList = new List[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            adjList[from].add(to);
            adjList[to].add(from);
        }
        
        // step 2: calculate the number of cc
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                countCCHelper(i, adjList, visited);
            }
        }
        
        return result;
    }
    
    private void countCCHelper(int node, List[] adjList, boolean[] visited) {
        if (visited[node]) {
            return;
        }
        
        visited[node] = true;
        
        List<Integer> neighbors = adjList[node];
        
        for (int neighbor : neighbors) {
            countCCHelper(neighbor, adjList, visited);
        }
    }
}

A BFS Solution:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 0 || edges == null) {
            return 0;
        }
        
        if (n == 1 && edges.length == 0) {
            return 1;
        }
        
        int result = 0;
        boolean[] visited = new boolean[n];
        
        // step 1: create the adj list from edge list
        List[] adjList = new List[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            adjList[from].add(to);
            adjList[to].add(from);
        }
        
        // step 2: calculate the number of cc
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                countCCHelper(i, adjList, visited, queue);
            }
        }
        
        return result;
    }
    
    private void countCCHelper(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {
        fill(node, adjList, visited, queue);
        
        while (!queue.isEmpty()) {
            int currNode = queue.poll();
            List<Integer> neighbors = adjList[currNode];
            
            for (Integer neighbor : neighbors) {
                fill(neighbor, adjList, visited, queue);
            }
        }
    }
    
    private void fill(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {
        if (visited[node]) {
            return;
        }
        
        visited[node] = true;
        
        queue.offer(node);
    }
}

Union-find solution:

private int[] father;
public int countComponents(int n, int[][] edges) {

    Set<Integer> set = new HashSet<Integer>();
    father = new int[n];
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < edges.length; i++) {
         union(edges[i][0], edges[i][1]);
    }

    for (int i = 0; i < n; i++){ 
        set.add(find(i));
    }
    return set.size();
}

int find(int node) {
    if (father[node] == node) {
        return node;
    }
    father[node] = find(father[node]);
    return father[node];
}

void union(int node1, int node2) {
    father[find(node1)] = find(node2);
}