323. Number of Connected Components In An Undirected Graph - Explanation

Description

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [aᵢ, bᵢ] indicates that there is an edge between aᵢ and bᵢ in the graph.

Return the number of connected components in the graph.

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 <= aᵢ <= bᵢ < n
aᵢ != bᵢ
There are no repeated edges.

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number vertices and E is the number of edges in the graph.

Hint 1

Assume there are no edges initially, so we have n components, as there are that many nodes given. Now, we should add the given edges between the nodes. Can you think of an algorithm to add the edges between the nodes? Also, after adding an edge, how do you determine the number of components left?

Hint 2

We can use the Union-Find (DSU) algorithm to add the given edges. For simplicity, we use Union-Find by size, where we merge the smaller component into the larger one. The Union-Find algorithm inserts the edge only between two nodes from different components. It does not add the edge if the nodes are from the same component. How do you find the number of components after adding the edges? For example, consider that nodes 0 and 1 are not connected, so there are initially two components. After adding an edge between these nodes, they become part of the same component, leaving us with one component.

Hint 3

We create an object of the DSU and initialize the result variable res = n, which indicates that there are n components initially. We then iterate through the given edges. For each edge, we attempt to connect the nodes using the union function of the DSU. If the union is successful, we decrement res; otherwise, we continue. Finally, we return res as the number of components.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation - Building adjacency lists from edge lists for efficient traversal
Depth First Search (DFS) - Recursively exploring all reachable nodes from a starting point
Breadth First Search (BFS) - Level-by-level traversal using a queue to visit connected nodes
Union-Find (Disjoint Set Union) - Efficiently grouping nodes into sets with union and find operations

1. Depth First Search

Intuition

A connected component is a group of nodes where every node is reachable from any other node in that group.

Using DFS:

If we start DFS from an unvisited node, we will visit all nodes in its connected component
Every time we start DFS from a new unvisited node, we’ve found one new component

Algorithm

Build an adjacency list from the edges.
Maintain a visited array to track visited nodes.
Initialize components = 0.
For each node from 0 to n-1:
- If the node is not visited:
  - Run DFS from this node (mark all reachable nodes as visited)
  - Increment components by 1
Return components.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        visit = [False] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def dfs(node):
            for nei in adj[node]:
                if not visit[nei]:
                    visit[nei] = True
                    dfs(nei)

        res = 0
        for node in range(n):
            if not visit[node]:
                visit[node] = True
                dfs(node)
                res += 1
        return res

public class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; node++) {
            if (!visit[node]) {
                dfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

    private void dfs(List<List<Integer>> adj, boolean[] visit, int node) {
        visit[node] = true;
        for (int nei : adj.get(node)) {
            if (!visit[nei]) {
                dfs(adj, visit, nei);
            }
        }
    }
}

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        vector<bool> visit(n, false);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; ++node) {
            if (!visit[node]) {
                dfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

private:
    void dfs(const vector<vector<int>>& adj, vector<bool>& visit, int node) {
        visit[node] = true;
        for (int nei : adj[node]) {
            if (!visit[nei]) {
                dfs(adj, visit, nei);
            }
        }
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @returns {number}
     */
    countComponents(n, edges) {
        const adj = Array.from({ length: n }, () => []);
        const visit = Array(n).fill(false);

        for (const [u, v] of edges) {
            adj[u].push(v);
            adj[v].push(u);
        }

        const dfs = (node) => {
            for (const nei of adj[node]) {
                if (!visit[nei]) {
                    visit[nei] = true;
                    dfs(nei);
                }
            }
        };

        let res = 0;
        for (let node = 0; node < n; node++) {
            if (!visit[node]) {
                visit[node] = true;
                dfs(node);
                res++;
            }
        }
        return res;
    }
}

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        List<List<int>> adj = new List<List<int>>();
        bool[] visit = new bool[n];
        for (int i = 0; i < n; i++) {
            adj.Add(new List<int>());
        }
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; node++) {
            if (!visit[node]) {
                Dfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

    private void Dfs(List<List<int>> adj, bool[] visit, int node) {
        visit[node] = true;
        foreach (var nei in adj[node]) {
            if (!visit[nei]) {
                Dfs(adj, visit, nei);
            }
        }
    }
}

class Solution {
    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        val adj = Array(n) { mutableListOf<Int>() }
        val visit = BooleanArray(n)
        for ((u, v) in edges) {
            adj[u].add(v)
            adj[v].add(u)
        }

        fun dfs(node: Int) {
            for (nei in adj[node]) {
                if (!visit[nei]) {
                    visit[nei] = true
                    dfs(nei)
                }
            }
        }

        var res = 0
        for (node in 0 until n) {
            if (!visit[node]) {
                visit[node] = true
                dfs(node)
                res++
            }
        }
        return res
    }
}

class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var adj = Array(repeating: [Int](), count: n)
        var visit = Array(repeating: false, count: n)

        for edge in edges {
            let u = edge[0], v = edge[1]
            adj[u].append(v)
            adj[v].append(u)
        }

        func dfs(_ node: Int) {
            for nei in adj[node] {
                if !visit[nei] {
                    visit[nei] = true
                    dfs(nei)
                }
            }
        }

        var res = 0
        for node in 0..<n {
            if !visit[node] {
                visit[node] = true
                dfs(node)
                res += 1
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges in the graph.

2. Breadth First Search

Intuition

A connected component is a set of nodes where each node can reach the others.

Using BFS:

Starting BFS from an unvisited node will visit all nodes in that component
Each time we start BFS from a new unvisited node, we discover one new connected component

Algorithm

Build an adjacency list from the given edges.
Create a visited array to mark nodes that are already seen.
Initialize components = 0.
For every node from 0 to n-1:
- If the node is not visited:
  - Start BFS from this node
  - Mark all reachable nodes as visited
  - Increment components by 1
Return components.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        visit = [False] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def bfs(node):
            q = deque([node])
            visit[node] = True
            while q:
                cur = q.popleft()
                for nei in adj[cur]:
                    if not visit[nei]:
                        visit[nei] = True
                        q.append(nei)

        res = 0
        for node in range(n):
            if not visit[node]:
                bfs(node)
                res += 1
        return res

public class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; node++) {
            if (!visit[node]) {
                bfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

    private void bfs(List<List<Integer>> adj, boolean[] visit, int node) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        visit[node] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int nei : adj.get(cur)) {
                if (!visit[nei]) {
                    visit[nei] = true;
                    q.offer(nei);
                }
            }
        }
    }
}

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        vector<bool> visit(n, false);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; ++node) {
            if (!visit[node]) {
                bfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

private:
    void bfs(vector<vector<int>>& adj, vector<bool>& visit, int node) {
        queue<int> q;
        q.push(node);
        visit[node] = true;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (int nei : adj[cur]) {
                if (!visit[nei]) {
                    visit[nei] = true;
                    q.push(nei);
                }
            }
        }
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @returns {number}
     */
    countComponents(n, edges) {
        const adj = Array.from({ length: n }, () => []);
        const visit = Array(n).fill(false);

        for (const [u, v] of edges) {
            adj[u].push(v);
            adj[v].push(u);
        }

        const bfs = (node) => {
            const q = new Queue([node]);
            visit[node] = true;
            while (!q.isEmpty()) {
                const cur = q.pop();
                for (const nei of adj[cur]) {
                    if (!visit[nei]) {
                        visit[nei] = true;
                        q.push(nei);
                    }
                }
            }
        };

        let res = 0;
        for (let node = 0; node < n; node++) {
            if (!visit[node]) {
                bfs(node);
                res++;
            }
        }
        return res;
    }
}

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        List<List<int>> adj = new List<List<int>>();
        bool[] visit = new bool[n];
        for (int i = 0; i < n; i++) {
            adj.Add(new List<int>());
        }
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }

        int res = 0;
        for (int node = 0; node < n; node++) {
            if (!visit[node]) {
                Bfs(adj, visit, node);
                res++;
            }
        }
        return res;
    }

    private void Bfs(List<List<int>> adj, bool[] visit, int node) {
        Queue<int> q = new Queue<int>();
        q.Enqueue(node);
        visit[node] = true;
        while (q.Count > 0) {
            int cur = q.Dequeue();
            foreach (var nei in adj[cur]) {
                if (!visit[nei]) {
                    visit[nei] = true;
                    q.Enqueue(nei);
                }
            }
        }
    }
}

class Solution {
    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        val adj = Array(n) { mutableListOf<Int>() }
        val visit = BooleanArray(n)
        for ((u, v) in edges) {
            adj[u].add(v)
            adj[v].add(u)
        }

        fun bfs(node: Int) {
            val q: Queue<Int> = LinkedList()
            q.offer(node)
            visit[node] = true
            while (q.isNotEmpty()) {
                val cur = q.poll()
                for (nei in adj[cur]) {
                    if (!visit[nei]) {
                        visit[nei] = true
                        q.offer(nei)
                    }
                }
            }
        }

        var res = 0
        for (node in 0 until n) {
            if (!visit[node]) {
                bfs(node)
                res++
            }
        }
        return res
    }
}

class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var adj = Array(repeating: [Int](), count: n)
        var visit = Array(repeating: false, count: n)
        for edge in edges {
            let u = edge[0], v = edge[1]
            adj[u].append(v)
            adj[v].append(u)
        }

        func bfs(_ node: Int) {
            var q = Deque<Int>()
            q.append(node)
            visit[node] = true
            while !q.isEmpty {
                let cur = q.removeFirst()
                for nei in adj[cur] {
                    if !visit[nei] {
                        visit[nei] = true
                        q.append(nei)
                    }
                }
            }
        }

        var res = 0
        for node in 0..<n {
            if !visit[node] {
                bfs(node)
                res += 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges in the graph.

3. Disjoint Set Union (Rank | Size)

Intuition

Disjoint Set Union (DSU) groups nodes into connected components efficiently.

Start by assuming each node is its own component
When we process an edge (u, v):
- If u and v are already in the same set, nothing changes
- If they are in different sets, we merge them and the number of components decreases by 1
Using union by rank/size + path compression keeps operations fast

At the end, the number of remaining sets is the number of connected components.

Algorithm

Initialize DSU with n nodes, each node as its own parent.
Set components = n.
For each edge (u, v):
- If union(u, v) is successful (they were separate):
  - Decrement components by 1
Return components.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, node):
        cur = node
        while cur != self.parent[cur]:
            self.parent[cur] = self.parent[self.parent[cur]]
            cur = self.parent[cur]
        return cur

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.rank[pv] > self.rank[pu]:
            pu, pv = pv, pu
        self.parent[pv] = pu
        self.rank[pu] += self.rank[pv]
        return True

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        dsu = DSU(n)
        res = n
        for u, v in edges:
            if dsu.union(u, v):
                res -= 1
        return res

class DSU {
    int[] parent;
    int[] rank;

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int node) {
        int cur = node;
        while (cur != parent[cur]) {
            parent[cur] = parent[parent[cur]];
            cur = parent[cur];
        }
        return cur;
    }

    public boolean union(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) {
            return false;
        }
        if (rank[pv] > rank[pu]) {
            int temp = pu;
            pu = pv;
            pv = temp;
        }
        parent[pv] = pu;
        rank[pu] += rank[pv];
        return true;
    }
}

public class Solution {
    public int countComponents(int n, int[][] edges) {
        DSU dsu = new DSU(n);
        int res = n;
        for (int[] edge : edges) {
            if (dsu.union(edge[0], edge[1])) {
                res--;
            }
        }
        return res;
    }
}

class DSU {
public:
    vector<int> parent;
    vector<int> rank;

    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int node) {
        int cur = node;
        while (cur != parent[cur]) {
            parent[cur] = parent[parent[cur]];
            cur = parent[cur];
        }
        return cur;
    }

    bool unionSets(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) {
            return false;
        }
        if (rank[pv] > rank[pu]) {
            swap(pu, pv);
        }
        parent[pv] = pu;
        rank[pu] += rank[pv];
        return true;
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        DSU dsu(n);
        int res = n;
        for (auto& edge : edges) {
            if (dsu.unionSets(edge[0], edge[1])) {
                res--;
            }
        }
        return res;
    }
};

class DSU {
    /**
     * @param {number} n
     */
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = Array(n).fill(1);
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        let cur = node;
        while (cur !== this.parent[cur]) {
            this.parent[cur] = this.parent[this.parent[cur]];
            cur = this.parent[cur];
        }
        return cur;
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u);
        let pv = this.find(v);
        if (pu === pv) {
            return false;
        }
        if (this.rank[pv] > this.rank[pu]) {
            [pu, pv] = [pv, pu];
        }
        this.parent[pv] = pu;
        this.rank[pu] += this.rank[pv];
        return true;
    }
}

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @returns {number}
     */
    countComponents(n, edges) {
        const dsu = new DSU(n);
        let res = n;
        for (const [u, v] of edges) {
            if (dsu.union(u, v)) {
                res--;
            }
        }
        return res;
    }
}

public class DSU {
    private int[] parent;
    private int[] rank;

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int Find(int node) {
        int cur = node;
        while (cur != parent[cur]) {
            parent[cur] = parent[parent[cur]];
            cur = parent[cur];
        }
        return cur;
    }

    public bool Union(int u, int v) {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv) {
            return false;
        }
        if (rank[pv] > rank[pu]) {
            int temp = pu;
            pu = pv;
            pv = temp;
        }
        parent[pv] = pu;
        rank[pu] += rank[pv];
        return true;
    }
}

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        DSU dsu = new DSU(n);
        int res = n;
        foreach (var edge in edges) {
            if (dsu.Union(edge[0], edge[1])) {
                res--;
            }
        }
        return res;
    }
}

type DSU struct {
    parent []int
    rank   []int
}

func NewDSU(n int) *DSU {
    dsu := &DSU{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        dsu.parent[i] = i
        dsu.rank[i] = 1
    }
    return dsu
}

func (dsu *DSU) Find(node int) int {
    cur := node
    for cur != dsu.parent[cur] {
        dsu.parent[cur] = dsu.parent[dsu.parent[cur]]
        cur = dsu.parent[cur]
    }
    return cur
}

func (dsu *DSU) Union(u, v int) bool {
    pu := dsu.Find(u)
    pv := dsu.Find(v)
    if pu == pv {
        return false
    }
    if dsu.rank[pv] > dsu.rank[pu] {
        pu, pv = pv, pu
    }
    dsu.parent[pv] = pu
    dsu.rank[pu] += dsu.rank[pv]
    return true
}

func countComponents(n int, edges [][]int) int {
    dsu := NewDSU(n)
    res := n
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        if dsu.Union(u, v) {
            res--
        }
    }
    return res
}

class DSU(n: Int) {
    val parent = IntArray(n) { it }
    val rank = IntArray(n) { 1 }

    fun find(node: Int): Int {
        var cur = node
        while (cur != parent[cur]) {
            parent[cur] = parent[parent[cur]]
            cur = parent[cur]
        }
        return cur
    }

    fun union(u: Int, v: Int): Boolean {
        val pu = find(u)
        val pv = find(v)
        if (pu == pv) {
            return false
        }
        if (rank[pv] > rank[pu]) {
            parent[pu] = pv
        } else {
            parent[pv] = pu
            rank[pu] += rank[pv]
        }
        return true
    }
}

class Solution {
    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        val dsu = DSU(n)
        var res = n
        for (edge in edges) {
            val (u, v) = edge
            if (dsu.union(u, v)) {
                res--
            }
        }
        return res
    }
}

class DSU {
    var parent: [Int]
    var rank: [Int]

    init(_ n: Int) {
        parent = Array(0..<n)
        rank = Array(repeating: 1, count: n)
    }

    func find(_ node: Int) -> Int {
        var cur = node
        while cur != parent[cur] {
            parent[cur] = parent[parent[cur]]
            cur = parent[cur]
        }
        return cur
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        let pu = find(u)
        let pv = find(v)
        if pu == pv { return false }
        var rootU = pu
        var rootV = pv
        if rank[rootV] > rank[rootU] {
            swap(&rootU, &rootV)
        }
        parent[rootV] = rootU
        rank[rootU] += rank[rootV]
        return true
    }
}

class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        let dsu = DSU(n)
        var res = n
        for edge in edges {
            let u = edge[0], v = edge[1]
            if dsu.union(u, v) {
                res -= 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(V + (E * α(V)))$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges in the graph. $α()$ is used for amortized complexity.

Common Pitfalls

Forgetting Isolated Nodes

When there are no edges, each node is its own component. Solutions that only iterate through edges will miss nodes with no connections and return 0 instead of n.

# Wrong: misses isolated nodes
for u, v in edges:
    # only processes connected nodes

Building a Directed Graph Instead of Undirected

Edges must be added in both directions. Adding only adj[u].append(v) without adj[v].append(u) causes incomplete traversals and overcounts components.

Not Marking Nodes as Visited Before Exploring

In BFS/DFS, marking a node as visited only after processing (instead of when first discovered) can cause nodes to be added to the queue multiple times, leading to incorrect counts or infinite loops.