Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#323) before relying on it.

Number of Connected Components

An interactive visualization of the Union-Find (Disjoint Set) approach to counting connected components in an undirected graph. Watch how path compression and union by rank efficiently merge components.

Union-Find LeetCode 323 ↗ Medium

The Problem

You have n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph.

Return the number of connected components in the graph.

Interactive Visualization

Number of Nodes (n)

Edges (pairs, e.g. 0-1,1-2)

Preset

Speed:

Graph Visualization

Components: -

Code

fun countComponents(n: Int, edges: Array<IntArray>): Int {    val parent = IntArray(n) { it }    val rank = IntArray(n)    fun find(x: Int): Int {        var i = x        while (parent[i] != i) {            parent[i] = parent[parent[i]]; i = parent[i] }        return i }    fun union(x: Int, y: Int): Boolean {        var px = find(x); var py = find(y)        if (px == py) return false        if (rank[px] < rank[py]) {            val t = px; px = py; py = t }        parent[py] = px        if (rank[px] == rank[py]) rank[px]++        return true }    var components = n    for ((u, v) in edges) {        if (union(u, v))            components--    }    return components}

def countComponents(n, edges):    parent = list(range(n))    rank = [0] * n    def find(x):        while parent[x] != x:            parent[x] = parent[parent[x]]            x = parent[x]        return x    def union(x, y):        px, py = find(x), find(y)        if px == py:            return False        if rank[px] < rank[py]:            px, py = py, px        parent[py] = px        if rank[px] == rank[py]:            rank[px] += 1        return True    components = n    for u, v in edges:        if union(u, v):            components -= 1    return components

Status & Log

Press Step or Play to begin.

Union-Find State

How It Works

Key Insight

Instead of running BFS/DFS from every node (which requires building an adjacency list), we use Union-Find (Disjoint Set Union) to process edges one at a time. Each edge [u, v] merges the components containing u and v. We start with n components (each node is its own component) and decrement every time a union actually merges two distinct components.

The Algorithm

Initialize parent[i] = i and rank[i] = 0 for each node. Set components = n.
For each edge [u, v], call union(u, v).
find(x) follows parent pointers to the root, applying path compression (pointing nodes directly to their grandparent) along the way.
union(x, y) finds roots px and py. If they are the same, the nodes are already connected (return False). Otherwise, attach the smaller-rank tree under the larger-rank root (union by rank) and return True.
Each successful union decrements components by 1.
After processing all edges, components holds the answer.

Complexity

Time O(n · α(n))

Space O(n)

With path compression and union by rank, each find and union operation runs in amortized O(α(n)) time, where α is the inverse Ackermann function — effectively constant for all practical input sizes. We process each of the E edges once, so total time is O(E · α(n)). Space is O(n) for the parent and rank arrays.