Cycle Detection and Connectivity

Directed and undirected cycle detection, DSU-based cycle detection, connected components, strongly connected components, bridges, articulation points, and biconnected components.

Strongly connected components

Kosaraju's two-pass algorithm and Tarjan's low-link algorithm.

Low-link concepts

Discovery time, low value, DFS tree edge, back edge, bridge condition, and articulation-point conditions. Include worked graphs and edge cases for parallel edges.

low[u] is the smallest discovery time reachable from u's DFS subtree using at most one back edge. A tree edge p → u is a bridge when low[u] > tin[p] (nothing below u reaches p or above). A non-root vertex p is an articulation point when some child u has low[u] ≥ tin[p]; the root is one when it has at least two DFS children.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Bridge detection skips the edge id it arrived by rather than the parent vertex. With two parallel edges between the same pair, the second one is a genuine back edge that makes neither a bridge — skipping by vertex would wrongly report a bridge.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // --- SCC: Kosaraju vs Tarjan on the same directed graph
    int V = 8;
    vector<vector<int>> g(V), gr(V);
    for (auto [u, v] : vector<pair<int, int>>{{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {6, 5}, {6, 7}, {7, 6}}) { g[u].push_back(v); gr[v].push_back(u); }
    vector<int> order, compK(V, -1); vector<bool> seen(V, false);
    function<void(int)> d1 = [&](int u) { seen[u] = true; for (int v : g[u]) if (!seen[v]) d1(v); order.push_back(u); };
    for (int u = 0; u < V; ++u) if (!seen[u]) d1(u);
    int c = 0;
    function<void(int)> d2 = [&](int u) { compK[u] = c; for (int v : gr[u]) if (compK[v] == -1) d2(v); };
    for (int i = V - 1; i >= 0; --i) if (compK[order[i]] == -1) { d2(order[i]); ++c; }
    vector<int> tin(V, -1), low(V), compT(V, -1); stack<int> st; vector<bool> onStack(V, false); int timer = 0, ct = 0;
    function<void(int)> tarjan = [&](int u) {
        tin[u] = low[u] = timer++; st.push(u); onStack[u] = true;
        for (int v : g[u]) {
            if (tin[v] == -1) { tarjan(v); low[u] = min(low[u], low[v]); }
            else if (onStack[v]) low[u] = min(low[u], tin[v]);
        }
…

SCCs (Kosaraju): 3 -> {6,7} {0,1,2} {3,4,5}
Tarjan finds the same partition: true (3 components)
bridges (low-link): 1-3 4-6
bridges (remove each edge, count components): 1-3 4-6
articulation points (low-link): 1 3 4
articulation points (remove each vertex): 1 3 4

Quiz

? A tree edge p → u is a bridge exactly when…
+ low[u] > tin[p] :: Nothing in u's subtree reaches p or above.
- low[u] ≥ tin[p] :: That is the articulation-point condition for p.
- tin[u] > tin[p] :: Always true for a tree edge.
- low[p] > tin[u] :: Reversed.

? Why skip the arrival edge by id rather than by parent vertex?
+ With parallel edges, the second edge to the parent is a real back edge; skipping by vertex would miss it and report a false bridge. :: Edge ids handle multigraphs.
- It is faster. :: Same complexity.
- Vertex ids can be negative. :: No.
- To handle self-loops only. :: Parallel edges are the issue.

? Which algorithms find strongly connected components in O(V + E)? (select all that apply)
+ Kosaraju (two DFS passes, one on the reversed graph) :: Shown in the run.
+ Tarjan (one DFS with low-links and a stack) :: Shown in the run, same partition.
- Dijkstra :: Shortest paths.
- Kruskal :: Spanning trees.