THE SAME GRAPH, EVERY ALGORITHM
One structure underneath almost all of it: which things are already connected to which. Answer that in near-constant time and minimum spanning trees, island counting and account merging all collapse into the same four lines.
This is not a list of problems. It is 13 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDA priority queue for Prim (unit 02). Heaps is step 11 and not built yet; the Disjoint Set everything else leans on is taught here in unit 03.
13 PROBLEMS · 8 LINK TO A JUDGE · THE REST ARE CONCEPTS THE DRILLS COVER
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Deck 2 asked when a distance may be called final. This deck asks a smaller question over and over — are these two things already connected? — and almost everything here is an answer to it.
Every node must end up connected and no source or destination is named.
MST · PRIM OR KRUSKALO(E log E)You are handed {u, v, w} triples, or the graph converts to them cheaply.
KRUSKALO(E log E)Neighbours per node, and reshaping to an edge list would be wasted work.
PRIMO(E log V)Merges happen over time and you only ever query membership, never the route.
DISJOINT SETO(α(n))Components after each operation, islands appearing one at a time.
DSU + A COUNTERO(q · α(n))The maximum cell, the highest water level, the smallest sufficient ceiling.
ACTIVATE IN ORDER + DSUO(n² α)Two questions decide everything here. Is the graph dense or sparse — that picks Prim's form or Kruskal. And are the connections arriving over time — that is the signal for Disjoint Set rather than a fresh traversal per query.
SPARSE ⇒ KRUSKAL / PRIM+HEAP · QUERIES OVER TIME ⇒ DISJOINT SET
Thirteen units in three movements. Units 01–04 build the MST and the Disjoint Set it leans on; 05–10 are six problems that are all the same connectivity query in disguise; 11–13 change subject to strongly connected components, bridges and articulation points.
A connected undirected graph has N nodes. How many edges does any spanning tree of it contain, and why is the count fixed?
Exactly N − 1. Touch all N nodes with fewer and the graph is disconnected; use more and you have closed a cycle. Every algorithm in this deck is therefore the same shape: take edges until you hold N − 1 of them, refusing any that would close a cycle. Prim and Kruskal differ only in the order they consider edges — and the count gives you a free termination test.
You repeatedly need to answer ‘are these two nodes already in the same group?’ as groups keep merging. What does a plain DFS per query cost you?
A whole O(N + E) sweep, every single time. With q queries that is O(q·(N + E)), and the work is almost entirely repeated — the connectivity you computed last query is still true. Disjoint Set exists to keep that answer between queries, giving near-constant time per question. This is why unit 03 comes before the six problems that follow it: they are all the same query asked in a costume.
A spanning tree is any set of edges that touches every node and closes no cycle — which pins it at exactly n − 1 edges. The minimum one is whichever of those has the smallest total weight. That is the entire definition, and getting it exactly right is what stops the next four units from feeling arbitrary.
WHAT EXACTLY MAKES A SET OF EDGES A MINIMUM SPANNING TREE?
A connected graph has n nodes. How many edges does any spanning tree of it have?
Exactly n − 1, always, whatever the weights are. Add one more edge to a tree and you necessarily close a cycle; remove one and the graph falls into two pieces. That is why taken == n - 1 is a legitimate early exit in Kruskal — the count alone tells you that you are finished.
Two different edge sets of a graph both total 24, and 24 is the smallest total achievable. Which is the MST?
Uniqueness is not part of the definition. The lecture is careful about this: the moment two edges share a weight, several equally minimal trees can exist and every one is a correct answer. This is exactly why judge problems ask for the MST's weight and almost never for the edge list — the weight is unique even when the tree is not.
You built the MST of a weighted graph. Is the path it gives between two nodes also the shortest path between them?
The single most expensive confusion available right now, because you have just spent a whole deck on shortest paths. They optimise different things: Dijkstra minimises one path from a source; an MST minimises the sum over the whole edge set. An MST will happily route you the long way round between two nodes if that saves weight elsewhere in the graph.
Split the nodes into any two groups — any split at all. The edges with one end in each group cross the cut, and the cheapest of them is always safe: every spanning tree has to cross somewhere, and a tree that crossed only by a dearer edge could swap it for this one and get cheaper. That is the whole justification. Prim keeps one group and grows it; Kruskal takes the cheapest safe edge anywhere — same theorem, two schedules.
The statement wants every node connected at the lowest total cost, and names no source and no destination. No source means no shortest path — it is a spanning problem.
Two conditions, both required: touch all n nodes, and use exactly n − 1 edges. The edge count is what forces acyclicity, and connectivity is what forces it to span. Verify both and you have a spanning tree; among all of those, the cheapest is the MST.
// A spanning tree is exactly two things: n-1 edges, and all n nodes // reachable. Either check alone passes graphs that are not spanning trees. bool isSpanningTree(int n, vector<pair<int,int>>& tree) { if ((int)tree.size() != n - 1) return false; // more => a cycle // fewer => disconnected vector<vector<int>> adj(n); for (auto &[u, v] : tree) { adj[u].push_back(v); adj[v].push_back(u); } vector<bool> seen(n, false); queue<int> q; q.push(0); seen[0] = true; int reached = 1; while (!q.empty()) { int v = q.front(); q.pop(); for (int nb : adj[v]) if (!seen[nb]) { seen[nb] = true; reached++; q.push(nb); } } return reached == n; // SPANNING means every node, not most of them }
// A spanning tree is exactly two things: n-1 edges, and all n nodes // reachable. Either check alone passes graphs that are not spanning trees. boolean isSpanningTree(int n, int[][] tree) { if (tree.length != n - 1) return false; // more => a cycle; fewer => split List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : tree) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } boolean[] vis = new boolean[n]; Deque<Integer> st = new ArrayDeque<>(); st.push(0); vis[0] = true; int seen = 1; while (!st.isEmpty()) { for (int to : adj.get(st.pop())) if (!vis[to]) { vis[to] = true; seen++; st.push(to); } } return seen == n; // n-1 edges AND connected }
# A spanning tree is exactly two things: n-1 edges, and all n nodes # reachable. Either check alone passes graphs that are not spanning trees. def is_spanning_tree(n, tree): if len(tree) != n - 1: # more => a cycle return False # fewer => disconnected adj = [[] for _ in range(n)] for u, v in tree: adj[u].append(v) adj[v].append(u) seen = [False] * n seen[0] = True q = deque([0]) reached = 1 while q: v = q.popleft() for nb in adj[v]: if not seen[nb]: seen[nb] = True reached += 1 q.append(nb) return reached == n # SPANNING means every node
Checking only the edge count is the trap that looks like diligence. A graph can have exactly n − 1 edges and still be wrong — a triangle plus a detached node has 3 edges for 4 nodes, satisfying the count while being both cyclic and disconnected. Both conditions, always.
Prim's grows one single tree outward from an arbitrary start. At every step it takes the cheapest edge that leaves the tree and reaches somewhere new. No sorting and no disjoint set — a priority queue of frontier edges is the whole apparatus.
HOW DO YOU GROW A MINIMUM SPANNING TREE OUTWARD FROM A SINGLE NODE?
At what moment does Prim's commit a node to the MST for good?
On the pop, guarded by if (inMST[v]) continue;. A node gets pushed once for every edge that reaches it, at several different weights. The priority queue guarantees the cheapest of those copies surfaces first; every later copy is stale and must be discarded. Marking on push instead would commit whichever edge happened to be seen first.
Someone adapts their Dijkstra into Prim's but leaves the push line untouched: pq.push({dist[v] + nw, nb}). What have they built?
This is the difference between the two algorithms, and it is one term. Prim's pushes nw — the edge's own weight, because it only cares what it costs to attach that node to the tree. Dijkstra pushes dist[v] + nw, the accumulated cost from the source. Both run, both terminate, both return a plausible number, and only one of them is an MST — which is what makes it expensive.
Step the visualiser on the previous slide to the end. What total does Prim's produce on this deck's graph?
24 — and starting from a different node does not change it. The start node decides the order edges get taken and can even change which edges are taken when weights tie, but the minimum total is a property of the graph. Kruskal reaches the same 24 by a completely different route, which is the point of running both on one picture.
No sorting and no DSU: keep one growing tree and always take the cheapest edge leaving it. Edges get considered in a different order than Kruskal uses — and the total comes out identical at 24.
You are asked for the weight of a minimum spanning tree and handed an adjacency list. When the graph arrives by neighbours rather than as a flat edge list, Prim's fits the input without reshaping it.
Keep one growing tree. The priority queue holds every edge currently leaving it, keyed by that edge's own weight. Pop the cheapest, and if it reaches somewhere new, absorb that node and push its outgoing edges. Stale entries — edges to nodes already absorbed — are discarded on the way out.
int spanningTree(int V, vector<vector<int>> adj[]) { // {weight, node} — the weight is the EDGE's cost to attach `node`, // NOT an accumulated distance from the start. That is the whole // difference between this and Dijkstra. priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<bool> inMST(V, false); int total = 0; pq.push({0, 0}); // any start node; first edge is free while (!pq.empty()) { auto [w, v] = pq.top(); pq.pop(); if (inMST[v]) continue; // a stale, more expensive copy — drop it inMST[v] = true; // FINAL only here, on the pop total += w; for (auto &e : adj[v]) { int nb = e[0], nw = e[1]; if (!inMST[nb]) pq.push({nw, nb}); // nw, not total + nw } } return total; }
// {weight, node} - the weight is the EDGE's cost to attach `node`, // NOT an accumulated distance from the start. That is the whole // difference between this and Dijkstra. public int spanningTree(int V, List<int[]>[] adj) { PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0])); boolean[] inMST = new boolean[V]; int total = 0; pq.add(new int[]{0, 0}); // start anywhere, cost 0 while (!pq.isEmpty()) { int[] top = pq.poll(); int w = top[0], node = top[1]; if (inMST[node]) continue; // a stale, pricier entry inMST[node] = true; total += w; // pay only when it joins for (int[] e : adj[node]) if (!inMST[e[0]]) pq.add(new int[]{e[1], e[0]}); // EDGE weight } return total; }
def spanning_tree(V, adj): # (weight, node) — the weight is the EDGE's cost to attach `node`, # NOT an accumulated distance from the start. That is the whole # difference between this and Dijkstra. pq = [(0, 0)] # any start node; first edge is free in_mst = [False] * V total = 0 while pq: w, v = heapq.heappop(pq) if in_mst[v]: # a stale, more expensive copy — drop it continue in_mst[v] = True # FINAL only here, on the pop total += w for nb, nw in adj[v]: if not in_mst[nb]: heapq.heappush(pq, (nw, nb)) # nw, not total + nw return total
Marking inMST[v] at push time instead of at pop is the bug that survives every small test. The node gets committed via whichever edge reached it first rather than the cheapest, so the total comes out too large — a plausible number, silently wrong, on a graph big enough to matter.
Disjoint Set answers one question — are these two already in the same group? — and performs one action: merge two groups. Both in effectively constant time. It is the most reused structure in this deck: every remaining unit except the last three is an application of it.
HOW DO YOU ANSWER 'ARE THESE TWO ALREADY CONNECTED?' IN NEAR-CONSTANT TIME?
In union by size, which root ends up as the parent?
The larger tree keeps its root, and the smaller one is hung beneath it. Do it the other way and every node in the big tree gets one level deeper — you would be paying the cost on the many to save it on the few. Hanging small under large means only the smaller group's nodes descend, which caps any node's depth at log n even before compression runs.
A student writes void unite(int a, int b) { par[b] = a; sz[a] += sz[b]; } with no find() calls. What breaks?
The single most common DSU bug there is. b may be deep inside its tree, so overwriting par[b] tears its existing subtree away from its real root and re-hangs it elsewhere. Nodes that were connected quietly stop being connected, and the sizes drift from reality. Resolve both to roots first — a = find(a); b = find(b); — then link. It never crashes; it just returns wrong answers.
Why is find() written to assign — return par[x] = find(par[x]); — rather than just returning the root it found?
That assignment is path compression, and it is half of why the structure is fast. Walking from a deep node to its root is expensive once; the assignment makes sure you never pay it again, because every node touched on the way now points straight at the root. A find that only reads is correct but leaves the tree exactly as tall as it was, and you drop from α(n) back to log n.
You need to report the number of connected components after each of q union operations. What is the cheapest way?
Start at n components and subtract one on every successful merge — which is precisely why unite is written to return a bool rather than void. A union whose two nodes already share a root changes nothing and must not decrement. This turns an O(q · (V+E)) loop into O(q · α(n)), and it is the shape of the next four problems in this deck.
Watch the forest rearrange. A union hangs the smaller tree under the larger one, and then find(8) compresses its whole path — every node on it jumps straight to the root. That flattening is why this is amortised α(n).
The statement merges things and then asks whether two of them ended up together — accounts, islands, network cables, stones. Anywhere connectivity changes over time and you only ever query membership, never the path.
Represent each group as a tree and identify it by its root. find walks to the root and flattens the path behind it; unite resolves both nodes to roots and hangs the smaller tree under the larger. Those two optimisations together make the amortised cost α(n), which is under 5 for any input that exists.
struct DSU { vector<int> par, sz; DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); } int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); // PATH COMPRESSION: the assignment } // is the optimisation, not the return bool unite(int a, int b) { a = find(a); // ALWAYS resolve to roots first — b = find(b); // linking raw nodes corrupts the forest if (a == b) return false; // already together; caller counts on this if (sz[a] < sz[b]) swap(a, b); // UNION BY SIZE: small hangs under large par[b] = a; sz[a] += sz[b]; return true; // a real merge happened } };
class DSU { int[] par, sz; DSU(int n) { par = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } } int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); // PATH COMPRESSION: the assignment } // is the optimisation, not the return boolean unite(int a, int b) { a = find(a); b = find(b); // ROOTS, never the raw nodes if (a == b) return false; // already together: caller learns nothing merged if (sz[a] < sz[b]) { int t = a; a = b; b = t; } // by SIZE par[b] = a; sz[a] += sz[b]; return true; } }
class DSU: def __init__(self, n): self.par = list(range(n)) self.sz = [1] * n def find(self, x): while self.par[x] != x: # path halving — same amortised bound as full compression, # and no recursion depth to worry about on 10**5 nodes self.par[x] = self.par[self.par[x]] x = self.par[x] return x def unite(self, a, b): a, b = self.find(a), self.find(b) # ALWAYS resolve to roots first — if a == b: # linking raw nodes corrupts it return False # already together if self.sz[a] < self.sz[b]: a, b = b, a # UNION BY SIZE: small under large self.par[b] = a self.sz[a] += self.sz[b] return True # a real merge happened
Using union by size without path compression, or the reverse, is the quiet one. Both are individually correct and both leave you at O(log n) per operation. Code that looks fully optimised then runs an order of magnitude slower than expected under 10⁵ queries — and nothing about the output says why.
Kruskal ignores the graph's shape entirely. Sort every edge by weight, walk the list once, and take each edge unless its two endpoints are already connected. Disjoint Set is the only reason that check is cheap — which is why it had to come first.
IF YOU ALWAYS TAKE THE CHEAPEST EDGE THAT DOES NOT CLOSE A CYCLE, IS THE RESULT MINIMAL?
Kruskal reaches an edge (u, v) and finds find(u) == find(v). What does that tell it?
Equal roots means a path between u and v already exists using edges taken earlier — and since the list is sorted, every one of those was cheaper. Adding this edge would create a cycle and buy nothing. Skip it. That one comparison is the whole cycle test, and without DSU it would be a graph traversal per edge.
Someone builds the edge list from an adjacency list with for u: for (v,w) in adj[u]: edges.push({w,u,v}) on an undirected graph. What goes wrong?
Each undirected edge appears in both endpoints' lists, so the list is 2E long. The total stays correct — the duplicate is rejected by the cycle check the second time — which is exactly why this survives testing and then costs you on a dense graph. Guard with if (u < v) and add each edge once.
Run the visualiser on the previous slide to completion. How many of this graph's ten edges get rejected, and what is the final total?
Exactly one: 2–3 flashes red, because by the time the sorted list reaches it, 2 and 3 are already joined through 1–4–5–6. Ten edges, seven taken, one rejected, and the walk stops early once the seventh is in — the last two are never examined. The total lands on 24, identical to Prim's, which is the cut property doing the work.
Sort every edge, then take it unless its endpoints are already connected. DSU is the only thing making that check fast. Rejected edges flash red; taken edges turn green and their weights fill in.
An MST weight is wanted and the graph is already an edge list, or converts to one cheaply. Kruskal never asks which nodes are adjacent — it only ever asks whether two nodes are already connected.
Sort every edge by weight and walk the list once. Take an edge only when its endpoints sit in different DSU groups; that is precisely the test for 'would this close a cycle'. After n − 1 successful takes the tree spans the graph and the rest of the list is irrelevant.
int spanningTree(int V, vector<vector<int>> adj[]) { vector<array<int,3>> edges; // {w, u, v} for (int u = 0; u < V; u++) for (auto &e : adj[u]) { int v = e[0], w = e[1]; if (u < v) edges.push_back({w, u, v}); // each edge ONCE } sort(edges.begin(), edges.end()); // by weight — the dominant cost DSU dsu(V); int total = 0, taken = 0; for (auto &[w, u, v] : edges) { // unite IS the cycle test: false means same root already if (!dsu.unite(u, v)) continue; total += w; if (++taken == V - 1) break; // a spanning tree is n-1 edges } return total; }
public int spanningTree(int V, List<int[]>[] adj) { List<int[]> edges = new ArrayList<>(); // {w, u, v} for (int u = 0; u < V; u++) for (int[] e : adj[u]) { int v = e[0], w = e[1]; if (u < v) edges.add(new int[]{w, u, v}); // each edge ONCE } edges.sort((x, y) -> Integer.compare(x[0], y[0])); // cheapest first DSU dsu = new DSU(V); int total = 0, taken = 0; for (int[] e : edges) { if (!dsu.unite(e[1], e[2])) continue; // same root => would cycle total += e[0]; if (++taken == V - 1) break; // n-1 edges is a tree } return total; }
def spanning_tree(V, adj): edges = [] for u in range(V): for v, w in adj[u]: if u < v: # each edge ONCE edges.append((w, u, v)) edges.sort() # by weight — the dominant cost dsu = DSU(V) total = taken = 0 for w, u, v in edges: # unite IS the cycle test: False means same root already if not dsu.unite(u, v): continue total += w taken += 1 if taken == V - 1: # a spanning tree is n-1 edges break return total
Calling unite before testing, then trying to undo it, is the trap — DSU has no undo. Once two trees are linked there is no cheap way to separate them. Let unite itself be the test: it returns false and changes nothing when the roots already match.
You need the minimum over paths of the maximum cell on the path — a minimax question, not a sum. Phrases like 'the water level at which you can swim across' or 'the smallest ceiling that still lets you through' all point here.
Turn time into the loop variable. Elevations on LC 778 are a permutation of 0 … n²−1, so at time t exactly the cells with elevation ≤ t are under water. Activate cells in elevation order, union each with its already-active neighbours, and the answer is the first t at which the two corners share a root.
int swimInWater(vector<vector<int>>& grid) { int n = grid.size(); // elevations are a permutation of 0..n*n-1, so this is a direct index: // cells[t] is the single cell that goes under water at time t vector<pair<int,int>> cells(n * n); for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) cells[grid[r][c]] = {r, c}; DSU dsu(n * n); vector<bool> on(n * n, false); int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; for (int t = 0; t < n * n; t++) { auto [r, c] = cells[t]; on[r * n + c] = true; // this cell is now swimmable for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (on[nr * n + nc]) // ONLY already-active neighbours dsu.unite(r * n + c, nr * n + nc); } if (dsu.find(0) == dsu.find(n * n - 1)) return t; // corners joined } return -1; // unreachable on a valid grid }
public int swimInWater(int[][] grid) { int n = grid.length; // elevations are a permutation of 0..n*n-1, so this is a direct index: // cells[t] is the single cell that goes under water at time t int[][] cells = new int[n * n][2]; for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) cells[grid[r][c]] = new int[]{r, c}; DSU dsu = new DSU(n * n); boolean[] on = new boolean[n * n]; int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1}; for (int t = 0; t < n * n; t++) { int r = cells[t][0], c = cells[t][1]; on[r * n + c] = true; // activate one cell for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (!on[nr * n + nc]) continue; // only ACTIVE neighbours dsu.unite(r * n + c, nr * n + nc); } if (dsu.find(0) == dsu.find(n * n - 1)) return t; // corners joined } return -1; }
def swimInWater(grid): n = len(grid) # elevations are a permutation of 0..n*n-1, so this is a direct index: # cells[t] is the single cell that goes under water at time t cells = [None] * (n * n) for r in range(n): for c in range(n): cells[grid[r][c]] = (r, c) dsu = DSU(n * n) on = [False] * (n * n) for t in range(n * n): r, c = cells[t] on[r * n + c] = True # this cell is now swimmable for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): if 0 <= nr < n and 0 <= nc < n and on[nr * n + nc]: dsu.unite(r * n + c, nr * n + nc) # ONLY active neighbours if dsu.find(0) == dsu.find(n * n - 1): # corners joined return t return -1 # unreachable on a valid grid
Unioning with every neighbour rather than only the active ones silently connects the corners early, and you return a t that is too small. A neighbour that exists is not a neighbour you may swim to — check on[nr][nc] before every union.
The walkthrough for #10 Swim in Rising Water. Watch it, then go straight back and write it yourself.
Deck 1 counted provinces with DFS. Nothing was wrong with that — but watch what happens when you count them with DSU instead: you never traverse anything. Start the count at n and drop it by one every time a union actually merges two different roots. The count is a side effect of building the structure.
HOW DOES A CONNECTED-COMPONENT COUNT FALL OUT OF DISJOINT SET FOR FREE?
Using DSU, where does the province count actually come from?
Both listed methods work, but the counter is the one the lecture builds because it is free — no extra pass at all. Every merge reduces the number of groups by exactly one, so maintaining the count during construction costs one subtraction. Counting self-parents afterwards is a correct fallback and an extra O(n) scan.
Someone writes for each edge: dsu.unite(i, j); count--;. What happens?
This is exactly why unite returns a bool. In a triangle 1–2, 2–3, 1–3 the third edge merges nothing, but this code still decrements — three nodes report 0 components. The decrement belongs inside the success branch: if (dsu.unite(i, j)) count--;
You already solve this fine with DFS. When does DSU genuinely become the better tool?
This is the reason the sheet re-solves a problem you have already done. On a static graph DFS is O(V+E) and perfectly good. But re-running DFS after each of q edge insertions is O(q · (V+E)); DSU absorbs each insertion in α(n) and always knows the answer. Every remaining problem in this deck is that shape — connectivity that changes.
Traversal unit 06 answers this by walking the graph; the disjoint set is told instead, one edge at a time, and traverses nothing. Watch the road 2–5: both ends already agree, so it does nothing at all. That is why the answer comes from counting the roots at the end rather than decrementing as you go.
You are given cables that already exist and asked to rewire. A cable whose two ends are already connected is redundant — it can be pulled out and used anywhere. So the question is only ever: how many spare cables do I have, and how many gaps do I need to close?
WHEN CAN A SET OF EXISTING CABLES BE REARRANGED TO CONNECT EVERYTHING?
With c components remaining after processing every cable, how many moves are needed?
Each move joins two components into one, so going from c down to 1 takes c − 1 moves. A common wrong answer is the number of spare cables — that is the supply, not the demand. The two are only related through the feasibility check.
Why can you check connections.size() < n - 1 and return −1 immediately, before touching the DSU?
It is not an optimisation — without it there is no −1 case at all, and you would return a positive number for an impossible input. Any connected graph on n nodes needs at least n−1 edges (§unit 01). If you hold fewer, no rearrangement can ever succeed, regardless of how they are currently placed.
You have n−1 cables exactly, and 3 components. Are there certainly enough spares?
A forest of c components spanning n nodes uses exactly n − c edges. Holding n−1 means you have (n−1) − (n−c) = c − 1 spares — precisely the number of moves needed, every time. That is why the supply never binds and the answer is simply c−1 once feasibility passes.
Unit 03's disjoint set with a different ending. Each cable is either load-bearing — it joins two separate groups — or redundant, both ends already connected, which is precisely what makes it free to move. Watch what the code never does: it counts the spares and then ignores the count. Cables used is n − c, so spares is m − (n − c), which is already at least c − 1 once you hold n−1 cables. The length check on the first line is the entire feasibility test.
You are handed cables that already exist and allowed to move them. Nothing is being built from scratch, so the question is a supply-and-demand one: how many spares, and how many gaps.
Union every cable. One whose endpoints already share a root is redundant and can be pulled out. Finish with c components and you need c − 1 moves — and if you were handed fewer than n−1 cables to begin with, no arrangement can work.
int makeConnected(int n, vector<vector<int>>& connections) { // n nodes need at least n-1 edges to be connected at all. Without this // check there is no -1 case and impossible inputs return a number. if ((int)connections.size() < n - 1) return -1; DSU dsu(n); int components = n; for (auto &e : connections) if (dsu.unite(e[0], e[1])) // only a REAL merge reduces the count components--; return components - 1; // one move closes one gap }
public int makeConnected(int n, int[][] connections) { // n nodes need at least n-1 edges to be connected at all. Without this // check there is no -1 case and impossible inputs return a number. if (connections.length < n - 1) return -1; DSU dsu = new DSU(n); int components = n; for (int[] e : connections) if (dsu.unite(e[0], e[1])) components--; // only a REAL merge counts return components - 1; // c components need c-1 cables }
def makeConnected(n, connections): # n nodes need at least n-1 edges to be connected at all. Without this # check there is no -1 case and impossible inputs return a number. if len(connections) < n - 1: return -1 dsu = DSU(n) components = n for a, b in connections: if dsu.unite(a, b): # only a REAL merge reduces the count components -= 1 return components - 1 # one move closes one gap
Returning the number of redundant cables instead of components − 1. They are different quantities that happen to coincide on the samples: spares are the supply, gaps are the demand, and only the demand is the answer.
The walkthrough for #05 Number of Operations to Make Network Connected. Watch it, then go straight back and write it yourself.
Two accounts belong to the same person if they share any single email. That is a connectivity question wearing a data-cleaning costume. The trick is choosing what the DSU nodes are: account indices, with a map from each email to the first account that claimed it supplying the edges.
HOW DO YOU MERGE RECORDS THAT SHARE ANY ONE FIELD?
What are the DSU's nodes in the lecture's solution?
Accounts, not emails. Emails are the evidence that two accounts belong together, and a hash map from email to its first owner turns that evidence into edges. Making emails the nodes also works but needs string-keyed DSU and a second map back to names — more machinery for the same answer.
A solution merges any two accounts that share the same name. What breaks?
The problem states plainly that two accounts may carry the same name and still be different people — only a shared email proves identity. The name is output, never input to the decision. This produces a confidently wrong answer on the sample, which is the cheapest possible place to learn it.
After all unions, how do you assemble the output?
DSU tells you which group, never who is in it — there are no child pointers to walk, only parents. So you invert it: one pass over every email, appending it to a bucket keyed by find(owner). The required sort is per bucket, and the name is read from any member since they now agree.
The nodes are strings, and that is the whole difficulty — a disjoint set indexes integers, so every address gets an id the first time it is seen. Union each account's addresses to its own first one and two accounts sharing even a single address collapse into one component without ever being compared. Watch the third John: it merges because of an address, and Mary stays separate despite the same machinery running over her.
Records that must be merged when they share any one field. The word 'merge' plus a shared identifier is a connectivity problem in disguise — the emails are evidence, not entities.
Make the DSU nodes the account indices. Walk every email keeping a map from the email to the first account that claimed it; a second sighting is an edge, so union the two accounts. At the end, bucket every email under its owner's root.
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) { int n = accounts.size(); DSU dsu(n); unordered_map<string,int> owner; // email -> FIRST account that claimed it for (int i = 0; i < n; i++) for (int j = 1; j < (int)accounts[i].size(); j++) { const string &mail = accounts[i][j]; if (owner.count(mail)) dsu.unite(i, owner[mail]); else owner[mail] = i; // the name is never consulted here } // DSU knows the group, not its members — invert it into buckets unordered_map<int, vector<string>> group; for (auto &[mail, idx] : owner) group[dsu.find(idx)].push_back(mail); vector<vector<string>> out; for (auto &[root, mails] : group) { sort(mails.begin(), mails.end()); vector<string> row{accounts[root][0]}; for (auto &m : mails) row.push_back(m); out.push_back(row); } return out; }
public List<List<String>> accountsMerge(List<List<String>> accounts) { int n = accounts.size(); DSU dsu = new DSU(n); Map<String, Integer> owner = new HashMap<>(); // email -> FIRST claimant for (int i = 0; i < n; i++) for (int j = 1; j < accounts.get(i).size(); j++) { String mail = accounts.get(i).get(j); Integer prev = owner.get(mail); if (prev == null) owner.put(mail, i); else dsu.unite(prev, i); // shared email => same person } Map<Integer, TreeSet<String>> bucket = new HashMap<>(); for (Map.Entry<String, Integer> e : owner.entrySet()) bucket.computeIfAbsent(dsu.find(e.getValue()), k -> new TreeSet<>()) .add(e.getKey()); // TreeSet sorts the emails List<List<String>> out = new ArrayList<>(); for (Map.Entry<Integer, TreeSet<String>> e : bucket.entrySet()) { List<String> row = new ArrayList<>(); row.add(accounts.get(e.getKey()).get(0)); // the name goes first row.addAll(e.getValue()); out.add(row); } return out; }
def accountsMerge(accounts): dsu = DSU(len(accounts)) owner = {} # email -> FIRST account that claimed it for i, acc in enumerate(accounts): for mail in acc[1:]: if mail in owner: dsu.unite(i, owner[mail]) else: owner[mail] = i # the name is never consulted here # DSU knows the group, not its members — invert it into buckets group = defaultdict(list) for mail, idx in owner.items(): group[dsu.find(idx)].append(mail) return [[accounts[root][0]] + sorted(mails) for root, mails in group.items()]
Merging on the name. The problem says explicitly that two different people may share a name — only a shared email proves identity. The name is output, never input to the decision, and this produces a confidently wrong answer rather than an error.
The walkthrough for #07 Accounts Merge. Watch it, then go straight back and write it yourself.
Land appears one cell at a time and the island count is wanted after every addition. Re-running a traversal per query is O(q · n · m) and will not pass. DSU handles each addition in α(n): a new cell adds one island, and every successful merge with a neighbour takes one back.
HOW DO YOU COUNT ISLANDS WHEN LAND APPEARS ONE CELL AT A TIME?
A new cell is added and has three neighbouring cells that are all already land and all in the same island. By how much does the island count change?
The new cell adds 1. The first neighbour merges successfully (−1); the second and third already share that root, so their unions return false and change nothing. Net 0. This is exactly why the count must key off the union's return value and not the number of neighbours.
The same position appears twice in the query list and the code processes it normally both times. What goes wrong?
The +1 happens before any union is attempted, so a repeat position inflates the count and the unions then find matching roots and correct nothing. Every subsequent answer is wrong by one. Guard at the top: if the cell is already land, push the current count and continue.
Why is a fresh DFS per query unacceptable here when it was fine for Number of Islands?
Nothing is wrong with DFS on a static grid — that is exactly what deck 1 used. The cost here is that the grid changes q times and DFS re-derives the whole answer from scratch each time, throwing away everything it learned. DSU keeps the answer up to date incrementally, which is the entire reason this problem sits in a DSU unit.
Every other island problem gets the grid up front and traverses it. Here land arrives one cell at a time and the answer is wanted after each arrival, which rules a traversal out. The arithmetic is the lesson: a new cell always adds one island, then each distinct neighbouring island it merges with takes one back — distinct, so two cells of the same island cost one merge, which is what find() is there to decide.
Land is added one cell at a time and an answer is wanted after every addition. 'After each query' plus 'how many components' is the online-connectivity signature, and it rules out re-traversal.
Keep a flat DSU over r·m + c. Each new cell provisionally adds one island; then for every already-land neighbour, a successful union takes one back. Record the count after each query.
vector<int> numIslands2(int n, int m, vector<vector<int>>& ops) { DSU dsu(n * m); vector<bool> land(n * m, false); vector<int> out; int count = 0; int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; for (auto &op : ops) { int r = op[0], c = op[1], id = r * m + c; // a repeated position must change NOTHING, or the count drifts up if (land[id]) { out.push_back(count); continue; } land[id] = true; count++; // provisionally its own island for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; if (!land[nr * m + nc]) continue; if (dsu.unite(id, nr * m + nc)) count--; // only a REAL merge } out.push_back(count); } return out; }
public List<Integer> numIslands2(int n, int m, int[][] ops) { DSU dsu = new DSU(n * m); boolean[] land = new boolean[n * m]; List<Integer> out = new ArrayList<>(); int count = 0; int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1}; for (int[] op : ops) { int r = op[0], c = op[1], id = r * m + c; // a repeated position must not add a second island if (land[id]) { out.add(count); continue; } land[id] = true; count++; // provisionally its own for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; if (!land[nr * m + nc]) continue; if (dsu.unite(id, nr * m + nc)) count--; // each real merge loses one } out.add(count); } return out; }
def numIslands2(n, m, ops): dsu = DSU(n * m) land = [False] * (n * m) out, count = [], 0 for r, c in ops: idx = r * m + c # a repeated position must change NOTHING, or the count drifts up if land[idx]: out.append(count) continue land[idx] = True count += 1 # provisionally its own island for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): if not (0 <= nr < n and 0 <= nc < m): continue if not land[nr * m + nc]: continue if dsu.unite(idx, nr * m + nc): # only a REAL merge count -= 1 out.append(count) return out
A repeated position in the query list. The +1 fires before any union is attempted, so a duplicate inflates the count permanently and every later answer is too high. Guard at the top of the loop, before incrementing.
The walkthrough for #08 Number of Islands II. Watch it, then go straight back and write it yourself.
Every zero is a candidate bridge between islands. Precompute all islands and their sizes once, then test each zero by summing the sizes of its distinct neighbouring islands. Two passes, no repeated traversal — and the deduplication is where nearly everyone loses a mark.
WHICH SINGLE ZERO, FLIPPED TO ONE, PRODUCES THE LARGEST ISLAND?
A zero has two neighbours that both belong to the same island of size 5. The code sums neighbour sizes without deduplicating. What does it report?
1 + 5 + 5 = 11, when flipping that cell really produces an island of 1 + 5 = 6. The same island reached through two different sides is still one island. Collect find(neighbour) into a set first, then sum over the set — never over the neighbour list.
Why are the islands built in a separate pass before any zero is examined?
Testing a zero by flipping it and running a traversal would be O(n²) per candidate and O(n⁴) overall. Building the DSU once gives every island a root with a known size, so a candidate costs four find calls. The whole solution lands at O(n²).
The grid is entirely ones. What does a loop that only considers zeros return?
The answer loop never executes, so whatever the accumulator was initialised to is returned — typically 0. The grid is already one island of n·n and that is the answer. Seed the result with the largest existing island before testing any candidate and the case resolves itself with no special branch.
Two passes. Label every island and record its size; then for each water cell sum the islands around it. The second pass hinges on one word: the neighbouring labels go into a set before they are summed, because a cell can touch the same island twice. Watch the flip at (1,1) — two land neighbours, one island, counted once. Adding per neighbouring cell instead looks right until an input has touching neighbours.
One flip allowed, and you are asked for the best achievable size. 'Change exactly one cell to maximise a component' means precompute the components, then price each candidate — never re-explore per candidate.
Build every island once with DSU so each root carries a size. Then for each zero, look at its four neighbours, collect their roots into a set, and the flipped size is 1 plus the sum over that set. Deduplication is the whole problem.
int largestIsland(vector<vector<int>>& grid) { int n = grid.size(); DSU dsu(n * n); int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; // PASS 1 — build every island so each root knows its size for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) { if (!grid[r][c]) continue; for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (grid[nr][nc]) dsu.unite(r * n + c, nr * n + nc); } } // seed with the biggest existing island: an all-ones grid has no zero to flip int best = 0; for (int i = 0; i < n * n; i++) if (dsu.find(i) == i) best = max(best, dsu.sz[i]); // PASS 2 — price every candidate flip for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) { if (grid[r][c]) continue; set<int> roots; // DISTINCT — the same island twice is once for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (grid[nr][nc]) roots.insert(dsu.find(nr * n + nc)); } int total = 1; for (int root : roots) total += dsu.sz[root]; best = max(best, total); } return best; }
public int largestIsland(int[][] grid) { int n = grid.length; DSU dsu = new DSU(n * n); int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1}; // PASS 1 - build every island so each root knows its size for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) { if (grid[r][c] == 0) continue; for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (grid[nr][nc] == 1) dsu.unite(r * n + c, nr * n + nc); } } int best = 0; for (int i = 0; i < n * n; i++) if (grid[i / n][i % n] == 1) best = Math.max(best, dsu.sz[dsu.find(i)]); // PASS 2 - each zero answers in O(1) from the precomputed sizes for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) { if (grid[r][c] == 1) continue; Set<Integer> roots = new HashSet<>(); // DEDUPE the neighbours int total = 1; for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; if (grid[nr][nc] == 0) continue; roots.add(dsu.find(nr * n + nc)); } for (int root : roots) total += dsu.sz[root]; best = Math.max(best, total); } return best; }
def largestIsland(grid): n = len(grid) dsu = DSU(n * n) # PASS 1 — build every island so each root knows its size for r in range(n): for c in range(n): if not grid[r][c]: continue for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): if 0 <= nr < n and 0 <= nc < n and grid[nr][nc]: dsu.unite(r * n + c, nr * n + nc) # seed with the biggest existing island: an all-ones grid has no zero to flip best = max((dsu.sz[i] for i in range(n * n) if dsu.find(i) == i), default=0) # PASS 2 — price every candidate flip for r in range(n): for c in range(n): if grid[r][c]: continue roots = set() # DISTINCT — the same island twice is once for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): if 0 <= nr < n and 0 <= nc < n and grid[nr][nc]: roots.add(dsu.find(nr * n + nc)) best = max(best, 1 + sum(dsu.sz[root] for root in roots)) return best
Summing neighbour sizes without deduplicating roots. A zero touching the same island on two sides counts it twice — 1+5+5 = 11 where the truth is 6. It inflates the answer on exactly the shapes the tests contain.
The walkthrough for #09 Making a Large Island. Watch it, then go straight back and write it yourself.
Stones in the same row or column can be removed down to one survivor per group. So the answer is n − (number of components). The elegant part is what you union: not stones with stones, but each stone's row with its column.
HOW MANY STONES CAN BE REMOVED IF EACH REMOVAL NEEDS A ROW OR COLUMN PARTNER?
Why is the answer n − components rather than n − 1?
Removal requires a partner sharing a row or column, so you can strip a component down until one stone remains — but never past it, and no stone can help across components. k components therefore leave k survivors, and n − k come off.
Someone unions row with col directly, with no offset. What breaks?
They share an index space. A stone at (3, 7) and a stone at (7, 3) would be joined through the shared node 3 and 7 despite having no row or column in common. Offset one space past the other's maximum — col + 10001 for this problem's bounds — so the two families of nodes can never collide.
Why union a row with a column at all, rather than comparing every pair of stones?
Pairwise is correct but quadratic. Every stone at (r, c) is evidence that row r and column c are in the same group, so a single union per stone captures all of it — every stone in row r is then transitively connected without ever being compared. n unions replace n²/2 comparisons.
Two stones are connected when they share a row or a column, and comparing every pair to discover that would be O(n²). So it is not done. Each stone is unioned with its row key and its column key instead — never with another stone — and anything sharing either key lands in one component transitively. The answer is n minus the component count, because exactly one stone per component has to stay behind.
Removal needs a partner sharing a row or a column. Whenever the rule is 'you may act while a neighbour remains', the answer is almost always total minus the number of independent groups.
Each group can be stripped to a single survivor and no further, so the answer is n − components. Rather than compare stones pairwise, note that a stone at (r, c) is itself the evidence that row r and column c belong together — so union those two, once per stone.
int removeStones(vector<vector<int>>& stones) { DSU dsu(20002); // rows 0..10000, cols offset above them unordered_set<int> used; for (auto &s : stones) { int r = s[0], c = s[1] + 10001; // OFFSET: row 3 and col 3 must differ dsu.unite(r, c); used.insert(r); used.insert(c); } unordered_set<int> roots; for (int node : used) roots.insert(dsu.find(node)); // every component leaves exactly one stone standing return stones.size() - roots.size(); }
public int removeStones(int[][] stones) { DSU dsu = new DSU(20002); // rows 0..10000, cols offset above them Set<Integer> used = new HashSet<>(); for (int[] s : stones) { int r = s[0], c = s[1] + 10001; // OFFSET: row 3 and col 3 must differ dsu.unite(r, c); used.add(r); used.add(c); } Set<Integer> roots = new HashSet<>(); for (int x : used) roots.add(dsu.find(x)); return stones.length - roots.size(); // each group leaves ONE survivor }
def removeStones(stones): dsu = DSU(20002) # rows 0..10000, cols offset above them used = set() for r, c in stones: c += 10001 # OFFSET: row 3 and col 3 must differ dsu.unite(r, c) used.add(r) used.add(c) roots = {dsu.find(node) for node in used} # every component leaves exactly one stone standing return len(stones) - len(roots)
Forgetting the column offset. Row 3 and column 3 then become the same DSU node, so a stone at (3, 7) and one at (7, 3) get joined despite sharing nothing. The count comes out too low and the answer too high — with no crash to warn you.
The walkthrough for #06 Most Stones Removed with Same Row or Column. Watch it, then go straight back and write it yourself.
A strongly connected component is a group where every node can reach every other — which only means anything on a directed graph. Kosaraju finds them in two passes and one reversal: order the nodes by finish time, flip every edge, then DFS in that order.
HOW DO YOU FIND GROUPS WHERE EVERY NODE CAN REACH EVERY OTHER, BOTH WAYS?
When is a node pushed onto the stack in Kosaraju's first pass?
After the recursive calls, not before. The stack must hold nodes in decreasing finish time, so that popping it gives a node from a source component of the condensation first. Push on entry instead and you get visit order, the guarantee collapses, and components silently merge.
Why does reversing every edge not change which nodes are strongly connected?
If u reaches v and v reaches u, both paths simply run backwards after reversal — so the SCCs are identical. What changes is the traffic between components: a one-way link A → B becomes B → A, so starting from a former source component the DFS can no longer leak into its neighbours, and it collects exactly one SCC.
Would running the second DFS on the original graph, in the same stack order, also work?
The order and the reversal are both load-bearing, and each is useless alone. The stack hands you a node in a component that can reach the others; on the original graph, DFS from there walks straight into all of them. Reversal is what turns those exits into entrances so the traversal is trapped in one component — which is precisely what you want to collect.
Watch the arrowheads. Pass 1 stacks nodes by finish time; then every edge flips, and each DFS from the stack top is trapped inside exactly one component. The reversal is the moment it clicks — the exits become entrances.
A directed graph and a question about mutual reachability — 'every node can reach every other within the group'. On an undirected graph this would just be connected components; direction is what makes it hard.
Two passes and a reversal. The first DFS records finish times on a stack, so popping it yields a node from a component nothing else points into. Reversing every edge leaves the components untouched but turns their exits into entrances, so a DFS from that node is trapped inside exactly one SCC.
int kosaraju(int V, vector<vector<int>>& adj) { vector<bool> vis(V, false); stack<int> order; // PASS 1 — push AFTER the recursion: this is finish order, not visit order function<void(int)> dfs1 = [&](int v) { vis[v] = true; for (int to : adj[v]) if (!vis[to]) dfs1(to); order.push(v); }; for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i); // reverse every edge: the SCCs survive, the links between them flip vector<vector<int>> rev(V); for (int v = 0; v < V; v++) for (int to : adj[v]) rev[to].push_back(v); // PASS 2 — each DFS on the transpose is trapped in exactly one SCC vis.assign(V, false); int scc = 0; function<void(int)> dfs2 = [&](int v) { vis[v] = true; for (int to : rev[v]) if (!vis[to]) dfs2(to); }; while (!order.empty()) { int v = order.top(); order.pop(); if (vis[v]) continue; dfs2(v); scc++; } return scc; }
public int kosaraju(int V, List<List<Integer>> adj) { boolean[] vis = new boolean[V]; Deque<Integer> order = new ArrayDeque<>(); // PASS 1 - push AFTER the recursion: this is finish order, not visit order for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i, adj, vis, order); List<List<Integer>> rev = new ArrayList<>(); // PASS 2 - reverse every edge for (int i = 0; i < V; i++) rev.add(new ArrayList<>()); for (int u = 0; u < V; u++) for (int v : adj.get(u)) rev.get(v).add(u); Arrays.fill(vis, false); int scc = 0; while (!order.isEmpty()) { // PASS 3 - in finish order int v = order.pop(); if (vis[v]) continue; dfs2(v, rev, vis); scc++; // one flood = one SCC } return scc; } private void dfs1(int v, List<List<Integer>> adj, boolean[] vis, Deque<Integer> order) { vis[v] = true; for (int to : adj.get(v)) if (!vis[to]) dfs1(to, adj, vis, order); order.push(v); // AFTER: its finish time } private void dfs2(int v, List<List<Integer>> rev, boolean[] vis) { vis[v] = true; for (int to : rev.get(v)) if (!vis[to]) dfs2(to, rev, vis); }
def kosaraju(V, adj): vis = [False] * V order = [] # PASS 1 — append AFTER the recursion: finish order, not visit order def dfs1(v): vis[v] = True for to in adj[v]: if not vis[to]: dfs1(to) order.append(v) for i in range(V): if not vis[i]: dfs1(i) # reverse every edge: the SCCs survive, the links between them flip rev = [[] for _ in range(V)] for v in range(V): for to in adj[v]: rev[to].append(v) # PASS 2 — each DFS on the transpose is trapped in exactly one SCC vis = [False] * V scc = 0 def dfs2(v): vis[v] = True for to in rev[v]: if not vis[to]: dfs2(to) for v in reversed(order): if not vis[v]: dfs2(v) scc += 1 return scc
Pushing onto the stack on entry instead of after the recursion. That records visit order rather than finish order, the source-component guarantee is lost, and separate components silently merge into one — a plausible, smaller answer with nothing to signal the error. Two links on this slide: LC 1520 is the problem the sheet pairs with this row and is a greedy interval question, not an SCC one — the GfG link is where you actually practise the algorithm above.
The walkthrough for #13 Kosaraju's Algorithm — Strongly Connected Components. Watch it, then go straight back and write it yourself.
A bridge is an edge whose removal disconnects the graph. Tarjan finds every one of them in a single DFS using two numbers per node: tin, when you arrived, and low, the earliest arrival time reachable from this subtree without using the edge you came in on.
WHICH EDGES, IF CUT, WOULD SPLIT THE GRAPH INTO PIECES?
What exactly does low[v] hold?
It is a time, not a node id, and the exclusion is the whole point. If some node beneath v can hop back to an ancestor via a back edge, that ancestor's early tin propagates up into low[v], proving an alternative route exists and the tree edge above v is therefore not a bridge.
A student writes if (low[child] >= tin[node]) when collecting bridges. What is reported?
low[child] == tin[node] means the child can climb back to this very node by another route — so the edge is redundant and removing it disconnects nothing. Strict > is required. The confusing part is that >= is exactly right for articulation points, one lecture later; the two rules differ by a single character and answer different questions.
Why must the parent edge be skipped by identity rather than by simply comparing node numbers?
A duplicate edge between u and v means the connection survives cutting either copy, so neither is a bridge. Skipping every neighbour equal to the parent hides the second copy, low never gets updated through it, and the edge is wrongly reported. Track the edge index you entered by and skip only that.
One DFS over a graph with a cycle and two chains. Every node gets tin on entry; low starts equal and gets pulled down by back edges. Every chain edge gets cut; not one edge of the cycle does — read the two rows under the graph and the rule does itself.
'Critical connection', 'the network splits if this link fails', 'find every edge whose removal disconnects'. A question about edges whose loss matters is a bridge problem, and one DFS answers it.
Run a DFS recording tin[v], the time you arrived, and low[v], the earliest arrival time reachable from v's subtree without reusing the edge you came in on. If a child cannot reach any higher than the node itself, the edge between them is the only route — a bridge.
class Solution { vector<vector<pair<int,int>>> adj; // {neighbour, edge id} vector<int> tin, low; vector<vector<int>> out; int timer = 0; void dfs(int v, int inEdge) { tin[v] = low[v] = timer++; for (auto [to, id] : adj[v]) { // skip the edge we came in on BY ID — a parallel edge is a real // second route and must still be followed if (id == inEdge) continue; if (tin[to] != -1) { low[v] = min(low[v], tin[to]); // back edge: tin, not low } else { dfs(to, id); low[v] = min(low[v], low[to]); // STRICTLY greater: reaching v itself would mean another route if (low[to] > tin[v]) out.push_back({v, to}); } } } public: vector<vector<int>> criticalConnections(int n, vector<vector<int>>& conns) { adj.assign(n, {}); tin.assign(n, -1); low.assign(n, -1); for (int i = 0; i < (int)conns.size(); i++) { adj[conns[i][0]].push_back({conns[i][1], i}); adj[conns[i][1]].push_back({conns[i][0], i}); } dfs(0, -1); return out; } };
class Solution { List<int[]>[] adj; // {neighbour, edge id} int[] tin, low; List<List<Integer>> out = new ArrayList<>(); int timer = 0; void dfs(int v, int inEdge) { tin[v] = low[v] = timer++; for (int[] e : adj[v]) { int to = e[0], id = e[1]; // skip the edge we came in on BY ID - a parallel edge between the // same pair is a genuine second route and must NOT be skipped if (id == inEdge) continue; if (tin[to] != -1) { // already seen: back edge low[v] = Math.min(low[v], tin[to]); } else { dfs(to, id); low[v] = Math.min(low[v], low[to]); if (low[to] > tin[v]) // strictly greater: a BRIDGE out.add(Arrays.asList(v, to)); } } } }
def criticalConnections(n, connections): adj = [[] for _ in range(n)] for i, (a, b) in enumerate(connections): adj[a].append((b, i)) # {neighbour, edge id} adj[b].append((a, i)) tin = [-1] * n low = [0] * n out = [] timer = 0 def dfs(v, in_edge): nonlocal timer tin[v] = low[v] = timer timer += 1 for to, eid in adj[v]: # skip the edge we came in on BY ID — a parallel edge is a real # second route and must still be followed if eid == in_edge: continue if tin[to] != -1: low[v] = min(low[v], tin[to]) # back edge: tin, not low else: dfs(to, eid) low[v] = min(low[v], low[to]) # STRICTLY greater: reaching v itself would mean another route if low[to] > tin[v]: out.append([v, to]) dfs(0, -1) return out
Using >= instead of >. Equality means the child can climb back to this very node another way, so the edge is redundant, not critical — and you report bridges that are not. Confusingly, >= is exactly right for articulation points in the next unit.
The walkthrough for #11 Bridges in a Graph. Watch it, then go straight back and write it yourself.
An articulation point is a node whose removal disconnects the graph — the vertex version of the previous unit, computed by the same DFS with two small changes: the comparison loosens to >=, and the root is judged by how many DFS children it has.
WHICH NODES, IF REMOVED, WOULD SPLIT THE GRAPH INTO PIECES?
Why does the articulation test use >= where the bridge test used >?
The two tests ask different questions. If the child can climb back only as far as this node, cutting the edge leaves that alternate route intact — not a bridge. But deleting the node destroys the route too, so the child is stranded — an articulation point. Equality is exactly the case that separates them.
Why is the DFS root handled by a separate rule?
Every other node inherits the test from its parent edge; the root has none, and applying the comparison to it flags it almost always. The right question for the root is whether it is holding separate subtrees together: with two or more DFS children it is, and removing it splits them apart. With one, the rest of the graph stays connected without it.
Someone increments a counter each time the condition fires, then returns the count. What is wrong?
A node with three children can satisfy low[child] >= tin[node] for each of them and get counted three times, for one cut vertex. Set a boolean — isAP[node] = true — and count the marks afterwards. The same shape of bug as double-counting islands in unit 09.
Deliberately the same graph unit 12 used, because the pair is the lesson. The run starts at 6 rather than 1 so the case that separates the two tests actually happens: when it returns to 2, low[1] lands exactly on tin[2] — the subtree climbs back as far as 2 and no further. Cutting that edge leaves the route intact, so it is not a bridge; deleting the node destroys the route with it, so 2 is a cut vertex. And watch the root: 6 satisfies the same comparison and is still not an articulation point, which is why it needs a rule of its own.
'Which servers, if they fail, split the network' — the vertex form of the previous question. Same DFS, same two timestamps, two small changes to the rule.
Identical machinery to bridges. The comparison loosens to >=, because removing the node also destroys the route back to itself that saved the edge. The DFS root has no parent edge, so it is judged separately: it is a cut vertex only if it has two or more DFS children.
class Solution { vector<vector<int>> adj; vector<int> tin, low; vector<bool> isAP; int timer = 0, root = 0, rootKids = 0; void dfs(int v, int parent) { tin[v] = low[v] = timer++; for (int to : adj[v]) { if (to == parent) continue; if (tin[to] != -1) { low[v] = min(low[v], tin[to]); continue; } dfs(to, v); low[v] = min(low[v], low[to]); // >= not > : removing the NODE kills the route back to itself too if (low[to] >= tin[v] && v != root) isAP[v] = true; if (v == root) rootKids++; } } public: vector<int> articulationPoints(int n, vector<vector<int>>& edges) { adj.assign(n, {}); tin.assign(n, -1); low.assign(n, 0); isAP.assign(n, false); for (auto &e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } dfs(root, -1); // the root has no parent edge, so it is judged on its child count alone if (rootKids > 1) isAP[root] = true; vector<int> out; for (int i = 0; i < n; i++) if (isAP[i]) out.push_back(i); return out; } };
class Solution { List<Integer>[] adj; int[] tin, low; boolean[] isAP; int timer = 0, root = 0, rootKids = 0; void dfs(int v, int parent) { tin[v] = low[v] = timer++; for (int to : adj[v]) { if (to == parent) continue; if (tin[to] != -1) { // back edge low[v] = Math.min(low[v], tin[to]); } else { dfs(to, v); low[v] = Math.min(low[v], low[to]); // >= not > : reaching v ITSELF still strands `to` if v is removed if (low[to] >= tin[v] && v != root) isAP[v] = true; if (v == root) rootKids++; } } } // the root has no parent, so the >= test is meaningless for it: // it matters only when it has two or more DFS children // if (rootKids > 1) isAP[root] = true; }
def articulation_points(n, edges): adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b) adj[b].append(a) tin = [-1] * n low = [0] * n is_ap = [False] * n timer = 0 root = 0 root_kids = 0 def dfs(v, parent): nonlocal timer, root_kids tin[v] = low[v] = timer timer += 1 for to in adj[v]: if to == parent: continue if tin[to] != -1: low[v] = min(low[v], tin[to]) continue dfs(to, v) low[v] = min(low[v], low[to]) # >= not > : removing the NODE kills the route back to itself too if low[to] >= tin[v] and v != root: is_ap[v] = True if v == root: root_kids += 1 dfs(root, -1) # the root has no parent edge, so it is judged on its child count alone if root_kids > 1: is_ap[root] = True return [i for i in range(n) if is_ap[i]]
Counting instead of marking. A node with three qualifying children is counted three times for one cut vertex. Set isAP[v] = true and total the marks afterwards — the same double-counting shape as the distinct-roots trap in unit 09.
A statement gives you a weighted graph and asks for the cheapest set of connections that keeps every node reachable. What is it asking for, and what is it not?
An MST — and it is not a shortest-path problem. The distinction matters because the MST minimises the total weight of the chosen edges, while a shortest-path tree minimises each individual distance from a source. Those are different answers, and the path an MST gives you between two nodes is frequently not the shortest one. Unit 01's drill makes exactly this point; every wrong reach for Dijkstra here starts by missing it.
Kosaraju and Tarjan both find structure by running a DFS and watching numbers. What single quantity does each one actually rely on?
Kosaraju uses finish times; Tarjan uses low-link values. Kosaraju stacks nodes as their recursion completes, then walks the reversed graph in that order. Tarjan instead tracks, for each node, the earliest arrival time reachable from its subtree — and compares that against the node's own arrival to spot bridges and articulation points. Same traversal, two different bookkeeping ideas, and knowing which is which is most of what units 11 to 13 ask of you.
Every one of these returns a plausible number rather than crashing. That is what makes them expensive — the judge says no and the code looks fine.
par[b] = a without resolving both through find first re-hangs a node's whole subtree somewhere else. Groups that were connected quietly stop being connected, and the sizes drift. It never crashes.
The component count must only fall when a union actually merges. Edges inside a component still call unite, so a counter that ignores the return value walks below the true answer.
Union by size without path compression — or the reverse — is correct and leaves you at O(log n) per operation. The code looks fully optimised and runs an order of magnitude slow under 10⁵ queries.
A zero touching the same island on two sides must count it once. Summing the neighbour list instead of the set of distinct roots gives 1+5+5 = 11 where the answer is 6.
Bridges need low[child] > tin[v]; articulation points need >=. One character apart, both compile, both return a plausible list, and only one of them answers the question you were asked.
The stack must hold finish order, so the push belongs after the recursion. Push on entry and you get visit order, the source-component guarantee dies, and separate SCCs merge into one.
The slide to reopen the night before: every tool in this deck, its cost, and the sentence in the statement that selects it.
Thirteen units, 13 sheet problems, and underneath almost all of them one question asked in near-constant time — are these two already connected? If you remember one thing: reach for DSU the moment connectivity starts changing over time.
That completes Step 15. Graphs across three decks: traversal, shortest paths, and spanning trees with disjoint set.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.