What signals in a problem statement indicate the Cycle detection sub-pattern?

"return an edge that can be removed so the result is a tree"; "detect a cycle in an undirected graph"; "minimum number of cables to move"

Cycle detection (Union-Find (DSU) Sub-pattern)

Q: What makes Cycle detection different from other sub-patterns?

**Detect Cycle (undirected)** stops at the first failed union. **Redundant Connection** returns that edge. **Network Connected** needs at least n − 1 cables, then answers groups − 1. **Redundant Connection II** is **directed**: first check for a node with two parents (two candidate edges), then use the DSU to decide which candidate to drop.

Find the edge that closes a cycle, or count the edges that are spare.

Signals in the problem statement

›
"return an edge that can be removed so the result is a tree"
›
"detect a cycle in an undirected graph"
›
"minimum number of cables to move"

What makes it different

Detect Cycle (undirected) stops at the first failed union. Redundant Connection returns that edge. Network Connected needs at least n − 1 cables, then answers groups − 1. Redundant Connection II is directed: first check for a node with two parents (two candidate edges), then use the DSU to decide which candidate to drop.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Detect Cycle in an Undirected Graph
Basic Anchor·GeeksforGeeks
WalkthroughMedium
2
Redundant Connection
Basic Reinforcement·LeetCode #684
WalkthroughMedium
3
Number of Operations to Make Network Connected
Slight Variation·LeetCode #1319
WalkthroughMedium
4
Redundant Connection II
Medium·LeetCode #685
WalkthroughHard

Template

cycle-template.cpp

// Undirected cycle / redundant edge: an edge whose two ends already share a root closes a cycle.
// Uses the DSU from the Union-Find template.
vector<int> firstRedundantEdge(int n, const vector<vector<int>>& edges) {   // nodes 1..n
    DSU dsu(n + 1);
    for (auto& e : edges)
        if (!dsu.unite(e[0], e[1])) return e;     // already connected: this edge makes a cycle
    return {};
}

// How many cables to move so all n computers connect (Network Connected):
// spare edges = edges that closed a cycle; you need (groups - 1) of them.
int makeConnected(int n, const vector<vector<int>>& connections) {
    if ((int)connections.size() < n - 1) return -1;
    DSU dsu(n);
    for (auto& c : connections) dsu.unite(c[0], c[1]);
    return dsu.groups - 1;
}

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?

Connectivity / components Grouping / equivalence