Skip to content

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

Example 1:

img

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

Example 2:

img

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

Constraints:

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

Solution:

class Solution {
    int components = 0;
    public int countComponents(int n, int[][] edges) {
        boolean[] visited = new boolean[n];

        List<List<Integer>> adj = new ArrayList<List<Integer>>();

        for (int i = 0; i < n; i++){
            adj.add(new ArrayList<Integer>());
        }

        for (int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        for (int i = 0; i < n; i++){
            if (visited[i] == false){
                dfs(i, visited, adj);
                components++;
            }

        }

        return components;
    }

    private void dfs(int index, boolean[] visited, List<List<Integer>> adj){
        visited[index] = true;

        for (int next : adj.get(index)){
            if (visited[next] == false){
                dfs(next, visited, adj);
            }

        }
        return;
    }
}

// TC: O(V+E)
// SC: O(E)

UnionFind

class Solution {
    public int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);


        int result = n;
        for (int[] edge : edges){
            if (uf.isConnected(edge[0], edge[1]) == false){
                uf.union(edge[0], edge[1]);
                result--;
            }
        }


        return result;
    }

}

class UnionFind{
    int[] root;

    public UnionFind(int n){
        root = new int[n];
        for (int i = 0; i < n; i++){
            root[i] = i;
        }

    }

    public int find(int x){
        while(x != root[x]){
            x = root[x];
        }

        return x;
    }

    public void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY){
            root[rootY] = rootX; 
        }
    }

    public boolean isConnected(int x, int y){
        return find(x) == find(y);
    }
}
// TC: O(V+E)
// SC: O(V)