How it works
A disjoint-set structure maintains groups whose members are connected by accepted unions. Initially each integer identifier belongs to its own component. Join combines two components, while Find returns a representative used to test whether two identifiers currently belong to the same component.
Joining zero with one and one with two connects all three. Their representatives compare equal, while three remains separate. Attempting to join zero and two afterward returns false because no new component connection is needed. That return value is useful for detecting a redundant edge in an undirected connectivity process.
Find performs path compression by shortening parent links as it walks toward the root. Join attaches the smaller component beneath the larger one, using the size array. Together those policies avoid repeatedly maintaining long unnecessary chains. The important observable contract is component membership, not which particular identifier becomes the root.
This structure does not preserve the original graph edges or reconstruct a route between members. It answers connectivity under merges. Removing an edge or splitting a component is not supported by this simple implementation. Choose another representation if the application requires dynamic deletions or actual path explanations.
Practice by joining three with four, then joining the two larger components. Check pairwise connectivity before and after the final union. Avoid asserting a fixed root number in tests unless the API intentionally exposes that policy; assert that members expected to be connected share a representative.
Finally, validate the identifier range at a public boundary. This compact version assumes values from zero through count minus one. A domain using string names can map them to indices first. Keep that mapping stable and separate from the internal representative choices, so optimization details cannot accidentally become public entity identifiers.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
var sets = new DisjointSet(5);
Console.WriteLine(sets.Join(0, 1));
Console.WriteLine(sets.Join(1, 2));
Console.WriteLine(sets.Find(0) == sets.Find(2));
Console.WriteLine(sets.Find(0) == sets.Find(3));
Console.WriteLine(sets.Join(0, 2));
class DisjointSet {
private readonly int[] parent, size;
public DisjointSet(int count) { parent = Enumerable.Range(0, count).ToArray(); size = Enumerable.Repeat(1, count).ToArray(); }
public int Find(int value) {
while (value != parent[value]) { parent[value] = parent[parent[value]]; value = parent[value]; }
return value;
}
public bool Join(int left, int right) {
int a = Find(left), b = Find(right);
if (a == b) return false;
if (size[a] < size[b]) (a, b) = (b, a);
parent[b] = a; size[a] += size[b]; return true;
}
}
Expected output
True True True False False
Find returns a representative; the exact representative value is an implementation detail.