2Brute2Best
🔥0
01

Connectivity / components (Union-Find (DSU) Sub-pattern)

Count or test the groups that the given connections form.

Signals in the problem statement
  • ›

    "number of connected components"

  • ›

    "is it a valid tree"

  • ›

    "stones in the same row or column", "regions"

What makes it different

Union-Find (template) and Number of Connected Components count successful unions down from n. Graph Valid Tree needs exactly n − 1 edges and no failed union. Most Stones Removed unions a row with a column; the answer is stones − groups. Regions Cut by Slashes splits each cell into 4 triangles and unions them according to /, \ or space.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Union-Find (template)
    Basic Anchor·GeeksforGeeks
    Easy
  2. 2
    Number of Connected Components in an Undirected Graph
    Basic Reinforcement·LeetCode #323 Premium
    Medium
  3. 3
    Graph Valid Tree
    Slight Variation·LeetCode #261 Premium
    Medium
  4. 4
    Most Stones Removed with Same Row or Column
    Medium·LeetCode #947
    Medium
  5. 5
    Regions Cut By Slashes
    Pattern Transfer·LeetCode #959
    Medium

Template

dsu-template.cpp
// Union-Find (Disjoint Set Union) with path compression + union by size.
struct DSU {
    vector<int> parent, sz;
    int groups;
    DSU(int n) : parent(n), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);             // hang the smaller tree under the bigger one
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
};
Remember this · Union-Find (DSU)
Trigger
Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.
Think
Am I repeatedly merging groups and asking whether two things are in the same group?
Key question
What are the elements, and what does it mean to union two of them?
Union-Find (DSU) overviewCycle detection