323. Number of Connected Components in an Undirected Graph

Union-Find : union(int p, int q), find(int p)

time complexity: find: O(1), so overall: O(E)

space complexity: O(V)

class Solution {
    // union-find
    int count;
    int[] graph;
    int[] size;
    public int countComponents(int n, int[][] edges) {
        // initialize the array representation of graph;
        graph = new int[n];
        size = new int[n];
        for(int i = 0; i<graph.length; i++){
            graph[i] = i;
            size[i] = 1;
        }
        count = n;
        
        for(int[] edge : edges){
            union(edge[0], edge[1]);
        }
        return count;
    }
    
    private void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP!=rootQ){
            if(size[rootP]>size[rootQ]){
                graph[rootQ] = rootP;
            }else{
                graph[rootP] = rootQ;
            }
            int sum = size[rootP]+size[rootQ];
            size[rootQ]=sum;
            size[rootQ]=sum;
            count--;
        }
    }
    
    // find the root of vertex i
    private int find(int i){
        while(graph[i]!=i){
            // remember: reduce time complexity
            graph[i]=graph[graph[i]];
            i=graph[i];
        }
        return i;
    }
}

DFS=> build graph, then check the visited vertex

Complexity Analysis

Here EE = Number of edges, VV = Number of vertices.

• Time complexity: {O}(E + V)O(E+V).

  Building the adjacency list will take {O}(E)O(E) operations, as we iterate over the list of edges once, and insert each edge into two lists.

  During the DFS traversal, each vertex will only be visited once. This is because we mark each vertex as visited as soon as we see it, and then we only visit vertices that are not marked as visited. In addition, when we iterate over the edge list of each vertex, we look at each edge once. This has a total cost of {O}(E + V)O(E+V).

• Space complexity: {O}(E + V)O(E+V).

  Building the adjacency list will take {O}(E)O(E) space. To keep track of visited vertices, an array of size {O}(V)O(V) is required. Also, the run-time stack for DFS will use {O}(V)O(V) space.

class Solution {
    boolean[] visited;
    int count;
    public int countComponents(int n, int[][] edges) {
        visited = new boolean[n];
        List<Integer>[] graph = buildGraph(edges, n);
        
        for(int i=0; i<graph.length; i++){
            if(!visited[i]){
                count++;
                traverse(graph, i);
            }
        }
        return count;
        
    }
    
    private void traverse(List<Integer>[] graph, int curr){
        visited[curr]=true;
        for(int next: graph[curr]){
            if(!visited[next]){
                traverse(graph, next);
            }
        }
    }
    
    private List<Integer>[] buildGraph(int[][] edges, int n){
        List<Integer>[] graph = new LinkedList[n];
        for(int i = 0; i<graph.length; i++){
            graph[i] = new LinkedList<>();
        }
        
        for(int i=0; i<edges.length; i++){
            int from = edges[i][0];
            int to = edges[i][1];
            
            // undirected graph;
            graph[from].add(to);
            graph[to].add(from);
        }
        
        return graph;
    }
}