A disjoint-set (union–find) structure keeps track of a collection of elements partitioned into non-overlapping groups, and answers two questions almost instantly: which group is x in? and merge the groups of x and y. It is the engine behind Kruskal's MST, cycle detection and dynamic connectivity.

The problem: dynamic connectivity

n people are initially strangers. Two operations arrive in any order: makeFriends(x, y) — now x and y are in the same friend circle (friendship is transitive) — and areFriends(x, y) — are they in the same circle? Answer the queries as they come, with no knowledge of future operations.

Approach	`makeFriends`	`areFriends`	Problem
Adjacency list + DFS/BFS	O(1)	O(n + m) — traverse the graph	a query must explore the whole component
Adjacency matrix + DFS/BFS	O(1)	O(n²)	same, and n² memory
Store the component id of every node	Θ(n) — relabel one whole component	Θ(1)	every merge rewrites up to n labels
Disjoint set	≈ O(1) amortised	≈ O(1) amortised	—

Each set is a tree stored in a parent array; a root is its own parent

initially                 makeFriends(0, 1)        makeFriends(1, 3)
parent: 0 1 2 3           parent: 0 0 2 3          parent: 0 0 2 0

(0) (1) (2) (3)            (0)   (2) (3)              (0)    (2)
                            │                         / \
                           (1)                      (1) (3)

areFriends(0, 2): find(0)=0, find(2)=2 → No
areFriends(0, 3): find(0)=0, find(3)=0 → Yes

Basic implementation: parent array

make_set
parent[i] = i for every element — n singleton sets.
find(x)
Follow parent links until reaching an element that is its own parent; that root is the representative.
union(x, y)
rx = find(x), ry = find(y); if they differ, parent[ry] = rx.
areFriends(x, y)
find(x) == find(y).

Python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))       # every element starts as its own set

    def find(self, x):
        while self.parent[x] != x:         # climb to the root
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.parent[ry] = rx           # hang one tree under the other root

    def are_friends(self, x, y):
        return self.find(x) == self.find(y)

ds = DisjointSet(4)
ds.union(0, 1)                             # makeFriends
ds.union(1, 3)
for x, y in [(0, 2), (0, 1), (0, 3)]:
    print(f"areFriends({x}, {y}):", "Yes" if ds.are_friends(x, y) else "No")
print("parent:", " ".join(map(str, ds.parent)))

C++

#include <iostream>
#include <vector>
using namespace std;

class DisjointSet {
    vector<int> parent;
public:
    DisjointSet(int n) : parent(n) {
        for (int i = 0; i < n; i++) parent[i] = i;      // every element starts as its own set
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x];          // climb to the root
        return x;
    }
    void unite(int x, int y) {                         // "union" is a C++ keyword
        int rx = find(x), ry = find(y);
        if (rx != ry) parent[ry] = rx;                 // hang one tree under the other root
    }
    bool areFriends(int x, int y) { return find(x) == find(y); }
    const vector<int>& parents() const { return parent; }
};

int main() {
    DisjointSet ds(4);
    ds.unite(0, 1);                                    // makeFriends
    ds.unite(1, 3);
    int queries[3][2] = {{0, 2}, {0, 1}, {0, 3}};
    for (auto& q : queries)
        cout << "areFriends(" << q[0] << ", " << q[1] << "): " << (ds.areFriends(q[0], q[1]) ? "Yes" : "No") << "\n";
    cout << "parent:";
    for (int p : ds.parents()) cout << " " << p;
    cout << "\n";
}

Java

public class Main {
    static class DisjointSet {
        int[] parent;
        DisjointSet(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;   // every element starts as its own set
        }
        int find(int x) {
            while (parent[x] != x) x = parent[x];       // climb to the root
            return x;
        }
        void union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx != ry) parent[ry] = rx;              // hang one tree under the other root
        }
        boolean areFriends(int x, int y) { return find(x) == find(y); }
    }

    public static void main(String[] args) {
        DisjointSet ds = new DisjointSet(4);
        ds.union(0, 1);                                 // makeFriends
        ds.union(1, 3);
        int[][] queries = {{0, 2}, {0, 1}, {0, 3}};
        for (int[] q : queries)
            System.out.println("areFriends(" + q[0] + ", " + q[1] + "): " + (ds.areFriends(q[0], q[1]) ? "Yes" : "No"));
        StringBuilder sb = new StringBuilder("parent:");
        for (int p : ds.parent) sb.append(' ').append(p);
        System.out.println(sb);
    }
}

JavaScript

class DisjointSet {
    constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); }   // every element is its own set
    find(x) {
        while (this.parent[x] !== x) x = this.parent[x];   // climb to the root
        return x;
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx !== ry) this.parent[ry] = rx;               // hang one tree under the other root
    }
    areFriends(x, y) { return this.find(x) === this.find(y); }
}

const ds = new DisjointSet(4);
ds.union(0, 1);                                            // makeFriends
ds.union(1, 3);
for (const [x, y] of [[0, 2], [0, 1], [0, 3]])
    console.log(`areFriends(${x}, ${y}):`, ds.areFriends(x, y) ? "Yes" : "No");
console.log("parent:", ds.parent.join(" "));

Output

areFriends(0, 2): No
areFriends(0, 1): Yes
areFriends(0, 3): Yes
parent: 0 0 2 0

Time O(n) worst case per operation — the tree can degenerate into a chain · Space O(n)

Union by rank (or by size)

Keep an extra array rank that stores an upper bound on the height of each root's tree. When uniting two roots, make the root of the shorter tree a child of the taller one — the height does not grow. Only when both have equal rank does the merged tree get one level taller.

Attach the shallower tree under the deeper root — height grows only on a tie

rank[rx] < rank[ry]          rank[rx] > rank[ry]          rank[rx] == rank[ry]
parent[rx] = ry              parent[ry] = rx              parent[ry] = rx; rank[rx] += 1

    (ry)                         (rx)                         (rx)  rank+1
   /  │  \                      /  │  \                      /  │  \
 ...  ... (rx)                ...  ... (ry)                 ...  ... (ry)

Variant	What is compared	Guarantee
Union by rank	height bound of the two trees	height ≤ `log₂ n` → `find` is `O(log n)`
Union by size	number of elements in the two trees (attach smaller under larger)	same `O(log n)` bound; the size array is useful in its own right (component sizes)

Path compression

find(x) already visits every node on the path from x to the root. While it is there, re-point each of them directly at the root — the next find on any of them is a single step. The parent array is only ever changed in a way that keeps the same sets.

Path compression flattens the path that find() walks

before find(6)                      after find(6)

     (0)                               (0)
     / \                             / | \
   (1) (2)                         (1)(2)(4)        6 and 4 now point straight at 0;
         │                              │   \       5 still points at 4 (it was not on the path)
        (4)                            (3)  (6) …
       /   \
     (5)   (6)

Python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n                    # upper bound on the height of each root's tree
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression: point straight at the root
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                       # already in the same set
        if self.rank[rx] < self.rank[ry]:      # union by rank: shallower tree goes under the deeper root
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1                 # only a tie makes the tree taller
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

ds = DisjointSet(7)
for x, y in [(0, 1), (2, 3), (4, 5), (1, 3), (5, 6), (3, 5)]:
    ds.union(x, y)
print("parent after unions:", " ".join(map(str, ds.parent)))
print("find(6) =", ds.find(6))
print("parent after find(6):", " ".join(map(str, ds.parent)))
print("connected(2, 5):", "Yes" if ds.connected(2, 5) else "No")
print("connected(3, 6):", "Yes" if ds.connected(3, 6) else "No")
print("components:", ds.components)

C++

#include <iostream>
#include <vector>
using namespace std;

class DisjointSet {
    vector<int> parent, rnk;                      // rnk = upper bound on the height of each root's tree
public:
    int components;
    DisjointSet(int n) : parent(n), rnk(n, 0), components(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression: point straight at the root
        return parent[x];
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;               // already in the same set
        if (rnk[rx] < rnk[ry]) swap(rx, ry);      // union by rank: shallower tree goes under the deeper root
        parent[ry] = rx;
        if (rnk[rx] == rnk[ry]) rnk[rx]++;        // only a tie makes the tree taller
        components--;
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
    void printParents(const string& label) {
        cout << label << ":";
        for (int p : parent) cout << " " << p;
        cout << "\n";
    }
};

int main() {
    DisjointSet ds(7);
    int edges[6][2] = {{0, 1}, {2, 3}, {4, 5}, {1, 3}, {5, 6}, {3, 5}};
    for (auto& e : edges) ds.unite(e[0], e[1]);
    ds.printParents("parent after unions");
    cout << "find(6) = " << ds.find(6) << "\n";
    ds.printParents("parent after find(6)");
    cout << "connected(2, 5): " << (ds.connected(2, 5) ? "Yes" : "No") << "\n";
    cout << "connected(3, 6): " << (ds.connected(3, 6) ? "Yes" : "No") << "\n";
    cout << "components: " << ds.components << "\n";
}

Java

public class Main {
    static class DisjointSet {
        int[] parent, rank;                           // rank = upper bound on the height of each root's tree
        int components;
        DisjointSet(int n) {
            parent = new int[n]; rank = new int[n]; components = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);   // path compression: point straight at the root
            return parent[x];
        }
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;               // already in the same set
            if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }   // union by rank: shallower under deeper
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;     // only a tie makes the tree taller
            components--;
            return true;
        }
        boolean connected(int x, int y) { return find(x) == find(y); }
        String parents() {
            StringBuilder sb = new StringBuilder();
            for (int p : parent) sb.append(' ').append(p);
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        DisjointSet ds = new DisjointSet(7);
        int[][] edges = {{0, 1}, {2, 3}, {4, 5}, {1, 3}, {5, 6}, {3, 5}};
        for (int[] e : edges) ds.union(e[0], e[1]);
        System.out.println("parent after unions:" + ds.parents());
        System.out.println("find(6) = " + ds.find(6));
        System.out.println("parent after find(6):" + ds.parents());
        System.out.println("connected(2, 5): " + (ds.connected(2, 5) ? "Yes" : "No"));
        System.out.println("connected(3, 6): " + (ds.connected(3, 6) ? "Yes" : "No"));
        System.out.println("components: " + ds.components);
    }
}

JavaScript

class DisjointSet {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);             // upper bound on the height of each root's tree
        this.components = n;
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);   // path compression
        return this.parent[x];
    }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;                  // already in the same set
        if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];   // union by rank: shallower under deeper
        this.parent[ry] = rx;
        if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;     // only a tie makes the tree taller
        this.components--;
        return true;
    }
    connected(x, y) { return this.find(x) === this.find(y); }
}

const ds = new DisjointSet(7);
for (const [x, y] of [[0, 1], [2, 3], [4, 5], [1, 3], [5, 6], [3, 5]]) ds.union(x, y);
console.log("parent after unions:", ds.parent.join(" "));
console.log("find(6) =", ds.find(6));
console.log("parent after find(6):", ds.parent.join(" "));
console.log("connected(2, 5):", ds.connected(2, 5) ? "Yes" : "No");
console.log("connected(3, 6):", ds.connected(3, 6) ? "Yes" : "No");
console.log("components:", ds.components);

Output

parent after unions: 0 0 0 0 0 4 4
find(6) = 0
parent after find(6): 0 0 0 0 0 4 0
connected(2, 5): Yes
connected(3, 6): Yes
components: 1

Time O(α(n)) amortised per operation — effectively constant · Space O(n)

Optimisations used	Amortised cost per operation
none	O(n)
union by rank only	O(log n)
path compression only	O(log n)
both	O(α(n)) — the inverse Ackermann function, `≤ 4` for every `n` that fits in the universe

Detect a cycle in an undirected graph

Process the edges one by one. For edge (u, v): if u and v are already in the same set, this edge closes a cycle; otherwise unite them. This is also exactly the test Kruskal's algorithm uses to decide whether an edge may join the spanning tree.

Python

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def has_cycle(n, edges):
    ds = DisjointSet(n)
    for u, v in edges:
        if ds.find(u) == ds.find(v):                 # already connected → this edge closes a cycle
            print(f"edge {u}-{v}: already connected → cycle")
            return True
        ds.union(u, v)
        print(f"edge {u}-{v}: joined")
    return False

edges = [(0, 1), (1, 2), (2, 3), (3, 1)]
print("graph has a cycle:", "Yes" if has_cycle(4, edges) else "No")

C++

#include <iostream>
#include <vector>
using namespace std;

struct DisjointSet {
    vector<int> parent, rnk;
    DisjointSet(int n) : parent(n), rnk(n, 0) { for (int i = 0; i < n; i++) parent[i] = i; }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rnk[rx] < rnk[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rnk[rx] == rnk[ry]) rnk[rx]++;
        return true;
    }
};

bool hasCycle(int n, const vector<pair<int,int>>& edges) {
    DisjointSet ds(n);
    for (auto [u, v] : edges) {
        if (ds.find(u) == ds.find(v)) {              // already connected → this edge closes a cycle
            cout << "edge " << u << "-" << v << ": already connected → cycle\n";
            return true;
        }
        ds.unite(u, v);
        cout << "edge " << u << "-" << v << ": joined\n";
    }
    return false;
}

int main() {
    vector<pair<int,int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 1}};
    bool cyc = hasCycle(4, edges);
    cout << "graph has a cycle: " << (cyc ? "Yes" : "No") << "\n";
}

Java

public class Main {
    static class DisjointSet {
        int[] parent, rank;
        DisjointSet(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; }
        int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;
            if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
            return true;
        }
    }

    static boolean hasCycle(int n, int[][] edges) {
        DisjointSet ds = new DisjointSet(n);
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (ds.find(u) == ds.find(v)) {              // already connected → this edge closes a cycle
                System.out.println("edge " + u + "-" + v + ": already connected → cycle");
                return true;
            }
            ds.union(u, v);
            System.out.println("edge " + u + "-" + v + ": joined");
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 1}};
        boolean cyc = hasCycle(4, edges);
        System.out.println("graph has a cycle: " + (cyc ? "Yes" : "No"));
    }
}

JavaScript

class DisjointSet {
    constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.rank = new Array(n).fill(0); }
    find(x) { return this.parent[x] === x ? x : (this.parent[x] = this.find(this.parent[x])); }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
        this.parent[ry] = rx;
        if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
        return true;
    }
}

function hasCycle(n, edges) {
    const ds = new DisjointSet(n);
    for (const [u, v] of edges) {
        if (ds.find(u) === ds.find(v)) {                 // already connected → this edge closes a cycle
            console.log(`edge ${u}-${v}: already connected → cycle`);
            return true;
        }
        ds.union(u, v);
        console.log(`edge ${u}-${v}: joined`);
    }
    return false;
}

const edges = [[0, 1], [1, 2], [2, 3], [3, 1]];
const cyc = hasCycle(4, edges);
console.log("graph has a cycle:", cyc ? "Yes" : "No");

Output

edge 0-1: joined
edge 1-2: joined
edge 2-3: joined
edge 3-1: already connected → cycle
graph has a cycle: Yes

Time O(E · α(V)) · Space O(V)

Where disjoint sets are used

Interview Q&A

What is the amortised complexity of union–find with both optimisations, and what does α(n) mean?

Union by rank vs union by size — any difference?

How does path compression work and why doesn't it break the sets?

How would you detect a cycle in an undirected graph with union–find?

Why does Kruskal's algorithm rely on union–find?