Union-Find (Disjoint Set Union)

1. Number of Connected Components Medium

Problem

Given n nodes labelled 0 to n-1 and a list of undirected edges, return the number of connected components.

Approach

• Start with n components, one per node. Every edge that joins two different components lowers the count by one. Edges inside a component change nothing.
• The Count property does the whole job. There is no final pass to count distinct roots.
• DFS also solves this in O(V + E). It is a fine answer here, because all the edges are known up front. Say that. Then give the Union-Find version as the one that extends to streaming edges.

Solution

public static class ConnectedComponents
{
    /// <summary>Number of connected components in an undirected graph.</summary>
    /// <param name="n">Node count. Nodes are labelled 0 .. n-1.</param>
    /// <param name="edges">Undirected edges as [a, b] pairs.</param>
    /// <returns>The number of connected components.</returns>
    /// <example>CountComponents(5, [[0, 1], [1, 2], [3, 4]]) returns 2</example>
    public static int CountComponents(int n, int[][] edges)
    {
        var dsu = new DisjointSet(n);     // n nodes, so n separate sets to start

        // Invariant: dsu.Count = components among the edges seen so far.
        // [0] and [1] are the two endpoints of the pair.
        foreach (var edge in edges)
            dsu.Union(edge[0], edge[1]);  // only a real merge lowers dsu.Count

        return dsu.Count;
    }
}

Walkthrough

n = 5, edges [[0,1], [1,2], [3,4]]:

• Start. Five separate nodes. Count = 5.
• [0, 1]. Different roots, so merge. Count = 4.
• [1, 2]. Different roots, so merge. Count = 3.
• [3, 4]. Different roots, so merge. Count = 2.

Components are {0, 1, 2} and {3, 4}.

Reading the figure. Arrows point from a node to its parent. Green nodes are roots, and each root names one set. Blue nodes point to a parent. The thick green arrow is the link made in that step. Count the green nodes in any frame and you get Count.

Effectively O(E). Quote the α factor, then say “which is at most 4, so effectively linear”. That is the complete answer.

The related one-liner

public static class GraphValidTree
{
    /// <summary>
    /// A graph is a tree when it is connected and has exactly n-1 edges.
    /// Equivalently: n-1 edges and no edge is ever redundant.
    /// </summary>
    /// <param name="n">Node count. Nodes are labelled 0 .. n-1.</param>
    /// <param name="edges">Undirected edges as [a, b] pairs.</param>
    /// <returns>True if the edges form one tree over all n nodes.</returns>
    /// <example>IsTree(3, [[0, 1], [1, 2]]) returns true</example>
    public static bool IsTree(int n, int[][] edges)
    {
        // n - 1: a tree on n nodes has exactly one fewer edge than nodes.
        if (edges.Length != n - 1)
            return false;

        var dsu = new DisjointSet(n);     // n nodes, each its own set

        // Union is false on a cycle edge. With n - 1 edges and no cycle,
        // the graph must be connected. All stops at the first false.
        return edges.All(edge => dsu.Union(edge[0], edge[1]));
    }
}

If any Union returns false, that edge closed a cycle, so it is not a tree. With exactly n - 1 edges and no cycle, connectivity follows on its own. That two-fact argument is worth having ready. Note that LINQ’s All short-circuits, so it stops at the first cycle edge. A lambda with a side effect inside LINQ is fine here, but say you know it is unusual.

Edge cases to raise

• No edges: the answer is n.
• All nodes in one chain: the answer is 1.
• Duplicate edges: the second one is a no-op, since the endpoints already share a root.
• Self-loop [2, 2]: also a no-op. Correct.
• n = 0: the answer is 0. Zero-length arrays are legal in C#.

2. Redundant Connection Medium

Problem

A tree on n nodes had one extra edge added, which made exactly one cycle. Given the edge list, return the edge you can remove to restore a tree. If several answers exist, return the one that appears last in the input.

Approach

• Process the edges in the order given. The first edge whose two endpoints are already connected is the one that closes the cycle.
• The graph has exactly one extra edge. So that first failure is also the last such edge in the input. Scanning forwards and returning at once meets the tie-break rule with no extra logic.
• The bool from Union is the entire solution. This problem exists to test whether you have that return value.
• Nodes are labelled 1..n, so size the structure at n + 1.

Solution

public static class RedundantConnection
{
    /// <summary>The edge that closes the single cycle in a tree plus one edge.</summary>
    /// <param name="edges">Undirected edges over nodes 1..n, in input order.</param>
    /// <returns>The edge to remove: the last one in the input that closes a cycle.</returns>
    /// <exception cref="ArgumentException">No edge closes a cycle.</exception>
    /// <example>FindRedundant([[1, 2], [1, 3], [2, 3]]) returns [2, 3]</example>
    public static int[] FindRedundant(int[][] edges)
    {
        // Size by the largest label, so bad input cannot index past the end.
        // 0: labels start at 1, so 0 is a safe floor for the running max.
        int maxNode = 0;
        foreach (var edge in edges)
            maxNode = Math.Max(maxNode, Math.Max(edge[0], edge[1]));

        // + 1: nodes are 1-indexed, so slots 0..maxNode. Slot 0 is never used.
        var dsu = new DisjointSet(maxNode + 1);

        // Invariant: the edges before this one form a forest with no cycle.
        foreach (var edge in edges)
        {
            // Union returns false when both ends already share a root.
            // That means this edge creates a cycle.
            if (!dsu.Union(edge[0], edge[1]))
                return [edge[0], edge[1]];
        }

        throw new ArgumentException("no redundant edge: the graph is already a forest",
            nameof(edges));
    }
}

Walkthrough

[[1,2], [1,3], [2,3]]:

• [1, 2]. Find(1) = 1, Find(2) = 2. Different, so merge.
• [1, 3]. Find(1) = 1, Find(3) = 3. Different, so merge.
• [2, 3]. Find(2) = 1, Find(3) = 1. Same, so return [2, 3].

Reading the figure. Each box adds one input edge. A green edge joined two different sets. Gray edges were added in earlier steps. The dashed red edge connects 2 and 3, which already share root 1. Union returns false there, and that edge is the answer.

Why the sizing is the largest label plus one

A tree on n nodes has n - 1 edges. This graph has one more, so edges.Length == n. Many solutions just write new DisjointSet(edges.Length + 1), and that is correct under the promise. Nodes run from 1 to n, so the arrays need n + 1 slots. Slot 0 is allocated and never touched.

The version above scans for the largest label instead. It costs one extra pass. In return, input that breaks the promise gets a clear ArgumentException. With edges.Length + 1, a plain tree input would crash with IndexOutOfRangeException on the highest node. That is easy to miss on a small test.

Edge cases to raise

• The cycle is the very first pair of edges, such as [[1,2],[2,1]]: caught on the second edge.
• The extra edge is last: the common case. It works because scanning forwards finds it last too.
• A self-loop: Union(x, x) returns false at once, so it is reported. Ask whether self-loops can appear.
• Several cycles: the problem promises exactly one. Say what you rely on.
• No cycle at all: the method throws ArgumentException. Ask if null or an empty array is preferred.

3. Accounts Merge Medium

Problem

Each account is a name followed by a list of emails. Two accounts belong to the same person if they share at least one email. Merge them. Return each merged account as the name followed by its emails in sorted order. The same name may belong to different people.

The modelling decision

Approach

• Keep a Dictionary<string, int> from each email to the first account index that mentioned it.
• Scan the emails of an account. A new email is recorded as owned by this account. A seen email means union this account with the one that first claimed it.
• After the pass, walk the email map once. Put every email in a bucket keyed by Find(owner). Each bucket is one person.
• Sort each bucket with StringComparer.Ordinal and put the name in front. Any account in the group has the right name. The root index is handy.

Solution

public static class AccountsMerge
{
    /// <summary>Merges accounts that share any email address.</summary>
    /// <param name="accounts">Each entry is [name, email1, email2, ...].</param>
    /// <returns>One entry per person: [name, ...emails sorted ascending].</returns>
    /// <example>
    /// Merge([["A", "x@z"], ["B", "y@z"], ["A", "x@z", "w@z"]])
    /// returns [["A", "w@z", "x@z"], ["B", "y@z"]] in some order
    /// </example>
    public static List<List<string>> Merge(string[][] accounts)
    {
        var dsu = new DisjointSet(accounts.Length);   // one set per account to start
        var ownerOf = new Dictionary<string, int>();  // email -> first account index with it

        // Invariant: every email in accounts 0 .. index-1 has an owner, and
        // any two of those accounts that share an email are in one set.
        for (int index = 0; index < accounts.Length; index++)
        {
            // [1..]: skip slot 0, which is the name. The rest are emails.
            foreach (var email in accounts[index][1..])
            {
                // TryAdd is false when the email already has an owner.
                if (!ownerOf.TryAdd(email, index))
                    dsu.Union(index, ownerOf[email]);   // shared email: same person
            }
        }

        // Bucket every email under the root of the account that owns it.
        var groups = new Dictionary<int, List<string>>();
        foreach (var (email, owner) in ownerOf)
        {
            int root = dsu.Find(owner);
            if (!groups.TryGetValue(root, out var bucket))
                groups[root] = bucket = [];
            bucket.Add(email);
        }

        // Every account in a group carries the same name, so the root's will do.
        // [0]: the name is the first entry of an account.
        // Ordinal: plain char-code order, the same on every machine and culture.
        return [.. groups.Select(g =>
            (List<string>)[accounts[g.Key][0], .. g.Value.Order(StringComparer.Ordinal)])];
    }
}

Walkthrough

Accounts [["A","x@z"], ["B","y@z"], ["A","x@z","w@z"]]:

• Account 0, x@z. New, so owner is 0.
• Account 1, y@z. New, so owner is 1.
• Account 2, x@z. Seen, so Union(2, 0).
• Account 2, w@z. New, so owner is 2.

Accounts 0 and 2 now share a root, so their emails land in one bucket. Account 1 stands alone.

Reading the figure. Boxes on the left are accounts. Boxes in the middle are emails. Gray lines are emails seen for the first time, so they just record an owner. The amber line is x@z showing up a second time, which triggers Union(2, 0). Same color on the left means same root, and the right side shows the merged output.

E is the total number of emails. The Union-Find work is effectively linear, so the sort dominates. Name the sort as the bottleneck, not the merging. That is the sharp answer here.

Why two accounts with the same name are not merged

Edge cases to raise

• An account with no emails: [1..] is empty, so it adds nothing and disappears from the output. Ask whether it should appear as a bare name.
• A chain merge: 1 shares with 2, and 2 shares with 3, but 1 and 3 share nothing. All three merge by transitivity. This case rules out simple pairwise comparison.
• Two people with the same name and no shared email: they stay separate.
• The same email listed twice inside one account: harmless, since Union(i, i) is a no-op.

4. Number of Islands II Hard

Problem

You start with an m × n grid of water. Land is added one cell at a time. After each addition, report the current number of islands. Return the list of counts.

Why this is the Union-Find problem

Approach

• Flatten the 2D grid to 1D. Cell (r, c) becomes index r * n + c. Then the integer class works unchanged, with no tuple keys.
• Start Count at zero, because there is no land yet. This is why Count has a public setter.
• Adding land: add one to Count first, treating the new cell as its own island. Then union it with each of the four neighbours that is already land. Every successful union subtracts one, so the arithmetic settles itself.
• Guard against a repeated position. Adding land where land already exists must change nothing. Without the guard it would inflate the count.

Solution

public static class NumberOfIslandsII
{
    // The four neighbours of a cell: down, up, right, left.
    // Each pair is (row change, column change). 1 moves forward, -1 back, 0 stays.
    private static readonly (int Dr, int Dc)[] Directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];

    /// <summary>Island count after each land addition to an empty grid.</summary>
    /// <param name="m">Number of rows.</param>
    /// <param name="n">Number of columns.</param>
    /// <param name="positions">Cells [row, col] turned into land, in order.</param>
    /// <returns>The island count after each addition.</returns>
    /// <example>
    /// NumIslands2(3, 3, [[0, 0], [0, 1], [1, 2], [2, 1]]) returns [1, 1, 2, 3]
    /// </example>
    public static List<int> NumIslands2(int m, int n, int[][] positions)
    {
        // m * n: one slot per grid cell. checked: throw rather than wrap on overflow.
        var dsu = new DisjointSet(checked(m * n)) { Count = 0 };   // 0: all water at first

        var isLand = new bool[m, n];      // m rows of n cells, all false (water)
        var answer = new List<int>(positions.Length);   // one count per addition

        // Invariant: dsu.Count = number of islands among the land cells so far.
        foreach (var pos in positions)
        {
            int r = pos[0], c = pos[1];   // [0] is the row, [1] the column

            if (isLand[r, c])
            {
                answer.Add(dsu.Count);    // repeat position: nothing changes
                continue;
            }

            isLand[r, c] = true;
            dsu.Count++;                  // a brand new island, for the moment

            foreach (var (dr, dc) in Directions)
            {
                int nr = r + dr, nc = c + dc;   // the neighbour cell
                // 0 <= ... < m and 0 <= ... < n keep the neighbour inside the grid.
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && isLand[nr, nc])
                {
                    // Each successful merge takes the count back down by one.
                    // r * n + c flattens (row, col) to one id: n cells per row.
                    dsu.Union(r * n + c, nr * n + nc);
                }
            }

            answer.Add(dsu.Count);
        }

        return answer;
    }
}

Two C# details are worth a sentence. new bool[m, n] is a true rectangular array, one block of memory, indexed as isLand[r, c]. And checked(m * n) turns a silent 32-bit overflow into an OverflowException if the grid is huge.

Walkthrough

m = 3, n = 3, positions [[0,0], [0,1], [1,2], [2,1]]:

• [0, 0]. Count after +1 is 1. No land neighbours. Reported: 1.
• [0, 1]. Count after +1 is 2. Joins (0,0), so −1. Reported: 1.
• [1, 2]. Count after +1 is 2. Nothing adjacent. Reported: 2.
• [2, 1]. Count after +1 is 3. Nothing adjacent. Reported: 3.

Notice [1,2] is diagonal to [0,1], and diagonals do not connect.

Reading the figure. Each grid is the state after one addition. The cell with the amber border is the one just added. Cells of the same color belong to the same island. In frame 2 the new cell touches (0,0). One union succeeds, so the count goes up 1 and back down 1. In frame 3 the new cell only touches (0,1) at a corner, so it starts a new island.

k is the number of additions. Each one does at most four unions, so the work per addition is constant.

The optimistic counting trick

Edge cases to raise

• A repeat position: guarded, and the previous count is repeated.
• A cell that bridges two or three existing islands: handled by the optimistic count.
• A 1×1 grid: one addition gives [1].
• Empty position list: returns an empty list.
• Only the four cardinal directions connect. Confirm that diagonals do not.
• If m × n is huge but k is small, the full grid wastes memory. A Dictionary<(int, int), int> that maps each land cell to a small id avoids it. It costs a constant factor. Worth a sentence.