Vultr DocsLatest Content

Number of Connected Components in an Undirected Graph

Updated on 27 June, 2025
Number of Connected Components in an Undirected Graph header image

Problem Statement

In the domain of graph theory, we often encounter tasks that require determining structural properties of a graph. In this particular problem, we are presented with a graph that consists of n nodes, and a list of edges that define connections between these nodes. Each edge is represented as a pair [ai, bi], where ai and bi are the node identifiers indicating a direct link. The main task is to compute the number of connected components within this graph.

A connected component of an undirected graph is a subgraph in which any two nodes are connected to each other by paths, and which is connected to no additional nodes in the supergraph. Hence, you need to determine how many such distinct groups exist where nodes are directly or indirectly connected.

Examples

Example 1

Input:

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

Output:

2

Example 2

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.

Approach and Intuition

To address this problem, we can utilize either depth-first search (DFS), breadth-first search (BFS), or union-find (disjoint set union, DSU) data structures. Here's the high-level approach using DFS, which is intuitive and straightforward for problems involving connected components:

  1. Start by initializing a visited list or set to keep track of all nodes that have been explored.

  2. Create an adjacency list from the edges. This list is a dictionary where each key is a node and the values are the nodes directly connected to it.

  3. Initialize a counter for connected components.

  4. Iterate over each node:

    1. If the node has not been visited, increment your connected component counter.

    2. Perform a DFS starting from this node:

      1. Mark the node as visited.

      2. Visit all its adjacent, unvisited nodes recursively, marking them as visited.

      3. This step ensures that all nodes in this component are marked as visited.

  5. By the end of the iteration, the counter reflects the total number of connected components.

This method efficiently traverses the graph ensuring each node is checked systematically, and components are identified based on the reachability from each unvisited node. This is aligned with the constraints provided, where the maximum nodes are 2000, which makes DFS a feasible solution within the given limits.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int findRoot(vector<int> &parent, int node) {
        if (node == parent[node]) {
            return node;
        }
        
        return parent[node] = findRoot(parent, parent[node]);
    }
    
    int merge(vector<int> &parent, vector<int> &rank, int node1, int node2) {
        node1 = findRoot(parent, node1);
        node2 = findRoot(parent, node2);
        
        if (node1 == node2) {
            return 0;
        } else {
            
            if (rank[node1] > rank[node2]) {
                rank[node1] += rank[node2];
                parent[node2] = node1;
            } else {
                rank[node2] += rank[node1];
                parent[node1] = node2;
            }
            return 1;
        }
    }

    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> parent(n), rank(n);
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        
        int components = n;
        for (int j = 0; j < edges.size(); j++) {
            components -= merge(parent, rank, edges[j][0], edges[j][1]);
        }

        return components;
    }
};

In the provided C++ solution for counting the number of connected components in an undirected graph, the solution employs the Union-Find algorithm. This algorithm is well-suited for dynamic connectivity problems like this. Below is a breakdown of the solution steps:

  • findRoot Function:
    This function recursively finds the root of a node. If the node is its own parent, it is the root. If not, the function uses path compression during the recursive calls to flatten the structure, which speeds up future operations.

  • merge Function:
    This function takes two nodes, finds their roots, and determines if they belong to different sets. If they are from the same set, no action is needed. If from different sets, the nodes are merged. The smaller tree (by rank) is attached under the bigger tree to keep the data structure balanced, ensuring quicker future operations.

  • countComponents Function:
    This is the primary function:

    1. Initialize the parent vector where each node is its own parent.
    2. Initialize the rank vector with 1 for all elements to help keep the tree flat.
    3. Define an integer components equal to the number of nodes. Initially, each node is considered its own component.
    4. For each edge, attempt to merge the ends. If a merge is successful (the ends were from different components), decrease the count of components by one.

The efficiency of Union-Find with path compression and union by rank ensures that the function handles large graphs effectively. This method returns the count of separate connected components in the graph.

java 
public class Solution {

    private int root(int[] parent, int node) {
        if (node == parent[node]) {
            return node;
        }
        
        return parent[node] = root(parent, parent[node]);
    }
    
    private int unite(int[] parent, int[] rank, int x, int y) {
        x = root(parent, x);
        y = root(parent, y);
        
        if (x == y) {
            return 0;
        } else {
            if (rank[x] > rank[y]) {
                rank[x] += rank[y];
                parent[y] = x;
            } else {
                rank[y] += rank[x];
                parent[x] = y;
            }
            return 1;
        }
    }

    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        int[] rank = new int[n];
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        
        int components = n;
        for (int i = 0; i < edges.length; i++) { 
            components -= unite(parent, rank, edges[i][0], edges[i][1]);
        }

        return components;
    }
}

This solution outlines an approach to calculate the number of connected components in an undirected graph using the Union-Find algorithm.

  • Define Helper Functions:

    • root: This function determines the root of a node by following parent pointers until the root is reached and applies path compression to optimize future queries.
    • unite: This function unites two nodes. If the roots of the nodes are the same, it returns 0, indicating no new connection was formed. Otherwise, it merges the sets based on rank and returns 1, indicating a successful union.

  • Main Logic - countComponents Method:

    • Initialize arrays for parents and rank. Set each node as its own parent and start with a rank of 1.
    • Initialize components to n, the number of nodes, since initially, each node is its own component.
    • Iterate over the list of edges and apply the unite function. Subtract the result from components since each union reduces the number of components by one if union is successful.
    • Return the remaining number of components.

By using union by rank and path compression, this implementation efficiently performs both union and find operations, crucial for connectivity queries in dynamic graphs.

Comments

No comments yet.