SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Union-Find (Disjoint Sets) Visualizer

Every set is a tree; its root names the set. find walks up to the root. union points one root at the other. If both ends of an edge already share a root, that edge closes a cycle.

Start the Union-Find (Disjoint Sets) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(α(n))
Average timeO(α(n))
Worst timeO(α(n))
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Every node starts as its own set, so it is its own parent (root). 8 sets.
  2. Edge A-B: find the root of each end.
  3. find(A) walks A, find(B) walks B. Paths are compressed to point at the root.
  4. Join the sets: B now points to A (the root with the higher rank). 7 sets left.
  5. Edge C-D: find the root of each end.
  6. find(C) walks C, find(D) walks D. Paths are compressed to point at the root.
  7. Join the sets: D now points to C (the root with the higher rank). 6 sets left.
  8. Edge B-C: find the root of each end.
  9. find(B) walks B → A, find(C) walks C. Paths are compressed to point at the root.
  10. Join the sets: C now points to A (the root with the higher rank). 5 sets left.
  11. Edge E-F: find the root of each end.
  12. find(E) walks E, find(F) walks F. Paths are compressed to point at the root.
  13. Join the sets: F now points to E (the root with the higher rank). 4 sets left.
  14. Edge A-D: find the root of each end.
  15. find(A) walks A, find(D) walks D → C → A. Paths are compressed to point at the root.
  16. Both roots are A: A and D are already connected. This edge would close a cycle.
  17. Edge C-F: find the root of each end.
  18. find(C) walks C → A, find(F) walks F → E. Paths are compressed to point at the root.
  19. Join the sets: E now points to A (the root with the higher rank). 3 sets left.
  20. Edge G-H: find the root of each end.
  21. find(G) walks G, find(H) walks H. Paths are compressed to point at the root.
  22. Join the sets: H now points to G (the root with the higher rank). 2 sets left.
  23. Done. 2 sets, and A-D closed a cycle.

Try it with your own input →

Union-Find (disjoint sets) in Java, Python, C++, C and JavaScript

int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
boolean union(int a, int b) {
  int ra = find(a), rb = find(b);
  if (ra == rb) return false;
  if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
  parent[rb] = ra;
  if (rank[ra] == rank[rb]) rank[ra]++;
  return true;
}
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return False
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True
vector<int> parent, rnk;

int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
bool unite(int a, int b) {
  int ra = find(a), rb = find(b);
  if (ra == rb) return false;
  if (rnk[ra] < rnk[rb]) swap(ra, rb);
  parent[rb] = ra;
  if (rnk[ra] == rnk[rb]) rnk[ra]++;
  return true;
}
#define MAXN 100
int parent[MAXN], rnk[MAXN];

int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
int unite(int a, int b) {
  int ra = find(a), rb = find(b);
  if (ra == rb) return 0;
  if (rnk[ra] < rnk[rb]) { int t = ra; ra = rb; rb = t; }
  parent[rb] = ra;
  if (rnk[ra] == rnk[rb]) rnk[ra]++;
  return 1;
}
function find(parent, x) {
  if (parent[x] !== x) parent[x] = find(parent, parent[x]);
  return parent[x];
}
function union(parent, rank, a, b) {
  let ra = find(parent, a), rb = find(parent, b);
  if (ra === rb) return false;
  if (rank[ra] < rank[rb]) [ra, rb] = [rb, ra];
  parent[rb] = ra;
  if (rank[ra] === rank[rb]) rank[ra]++;
  return true;
}

In an interview

LeetCode 684, Redundant Connection, and 547 Number of Provinces. Kruskal’s MST is built on it.

Path compression (line 1) plus union by rank (line 7) make each operation almost O(1): α(n) is below 5 for any input that fits in memory. The label next to a node points at its parent; a ringed node with no label is a root.

More graphs