ix. SCC and 2-SAT

Strongly connected components partition a digraph into maximal mutually reachable sets; contracting them gives a DAG (the condensation), on which everything that cycles made hard becomes DP. 2-SAT is satisfiability of 2-literal clauses, decided by SCCs of the implication graph in linear time.

Tarjan (iterative, components in topological order)

struct SCC {
    int cnt = 0; vector<int> comp;                          // comp[v] in [0, cnt), topological order of the condensation
    SCC(const vector<vector<int>>& g) {
        int n = sz(g), timer = 0; comp.assign(n, -1);
        vector<int> tin(n, -1), low(n), it(n), stk, call;
        for (int r = 0; r < n; r++) {
            if (tin[r] >= 0) continue;
            tin[r] = low[r] = timer++; stk.push_back(r); call.push_back(r);
            while (sz(call)) {
                int u = call.back();
                if (it[u] < sz(g[u])) {
                    int v = g[u][it[u]++];
                    if (tin[v] < 0) { tin[v] = low[v] = timer++; stk.push_back(v); call.push_back(v); }
                    else if (comp[v] < 0) low[u] = min(low[u], tin[v]);   // v still on the stack
                    continue;
                }
                call.pop_back();
                if (sz(call)) low[call.back()] = min(low[call.back()], low[u]);
                if (low[u] == tin[u]) { int v; do { v = stk.back(); stk.pop_back(); comp[v] = cnt; } while (v != u); cnt++; }
            }
        }
        for (int& c : comp) c = cnt - 1 - c;                 // Tarjan emits sinks first
    }
    vector<vector<int>> dag(const vector<vector<int>>& g) const {   // condensation edges, deduplicated
        vector<vector<int>> d(cnt);
        for (int u = 0; u < sz(g); u++) for (int v : g[u]) if (comp[u] != comp[v]) d[comp[u]].push_back(comp[v]);
        for (auto& x : d) { sort(all(x)); x.erase(unique(all(x)), x.end()); }
        return d;
    }
};

Kosaraju is the two-pass alternative: DFS to get finishing order, then DFS on the reversed graph in decreasing finishing order; each tree is an SCC, found in topological order. Gabow’s is a one-pass alternative to Tarjan that replaces the low array with a second stack, slightly shorter code and marginally faster in practice.

	Passes	Extra arrays	Needs $G^T$	Component order
Kosaraju	2	order, used	yes	topological
Tarjan	1	tin, low, onStack	no	reverse topological
Gabow	1	tin, two stacks	no	reverse topological

All three are $O(n+m)$; check which direction your implementation emits before relying on it downstream.

Proof: Tarjan's lowlink identifies the SCC roots

Let the root of an SCC be its first discovered vertex. By the white-path theorem, all vertices of the SCC are descendants of the root, and they stay on the stack until the root finishes. ${\text{low}}_u$ is the smallest $\text{tin}$ reachable from $u$‘s subtree by tree edges followed by at most one edge to a vertex still on the stack. If $u$ is not a root, some vertex of $u$‘s subtree has an edge leading (through the SCC) back to a proper ancestor still on the stack, so ${\text{low}}_u<{\text{tin}}_u$. If $u$ is a root, every on-stack vertex reachable from its subtree belongs to its own SCC (a vertex on the stack below it with a path back would put it in an earlier SCC), so ${\text{low}}_u={\text{tin}}_u$. Hence popping the stack down to $u$ when ${\text{low}}_u={\text{tin}}_u$ outputs exactly $u$‘s SCC. SCCs are emitted when their root finishes, which is after every SCC reachable from it: reverse topological order.

The condensation

Question	Answer on the condensation
maximum weight collectible on a walk	DAG longest path with component weights (CSES Coin Collector)
all-pairs reachability	bitset DP over the DAG (DAGs)
minimum starting points so everything is reached	number of sources
minimum edges to add for strong connectivity	$\max (\#\text{sources},\#\text{sinks})$ if more than one SCC, else 0
vertices reachable from everyone	the unique sink component if there is exactly one, else none
2-SAT	compare component ids

Proof: the condensation is acyclic, and the $\max (s,t)$ formula

If components $C_1\to C_2\to \cdots \to C_1$ formed a cycle, all their vertices would be mutually reachable, contradicting maximality. Lower bound: in the final strongly connected graph every source component needs an incoming edge and every sink component an outgoing edge, and one new edge serves at most one of each, so at least $\max (s,t)$ edges are needed. Upper bound (Eswaran–Tarjan): match sources to sinks so that $p$ pairs $(s_i,t_i)$ have $s_i$ reaching $t_i$ with $p$ maximal; add edges $t_i\to s_{i+1}$ cyclically, which makes all matched sources and sinks one strongly connected piece; then connect each unmatched sink to some source and each unmatched source from some sink, pairing leftovers, for a total of $\max (s,t)$ edges. The careful case analysis (isolated components) is in their paper; in practice, constructing the edges is rarely required.

2-SAT

Variables $x_0..x_{n-1}$; literal $x_i$ is vertex $2i$, $\neg x_i$ is $2i+1$. Clause $(a\vee b)$ gives edges $\neg a\to b$ and $\neg b\to a$. Satisfiable iff no $x_i$ shares an SCC with $\neg x_i$; then set $x_i$ true iff $\text{comp}(x_i)$ comes after $\text{comp}(\neg x_i)$ in topological order.

struct TwoSat {
    int n; vector<vector<int>> g;
    TwoSat(int n) : n(n), g(2 * n) {}
    int lit(int i, bool val) { return 2 * i + !val; }
    void either(int a, bool va, int b, bool vb) {           // (x_a == va) OR (x_b == vb)
        g[lit(a, !va)].push_back(lit(b, vb)); g[lit(b, !vb)].push_back(lit(a, va));
    }
    void setValue(int a, bool v) { either(a, v, a, v); }
    void implies(int a, bool va, int b, bool vb) { either(a, !va, b, vb); }
    optional<vector<bool>> solve() {
        SCC s(g); vector<bool> res(n);
        for (int i = 0; i < n; i++) {
            if (s.comp[2 * i] == s.comp[2 * i + 1]) return nullopt;
            res[i] = s.comp[2 * i] > s.comp[2 * i + 1];
        }
        return res;
    }
};

Constraint	Clauses
$a$ / $\neg a$	$(a\vee a)$ / $(\neg a\vee \neg a)$
$a\Rightarrow b$	$(\neg a\vee b)$
$a=b$	$(\neg a\vee b)(a\vee \neg b)$
$a\ne b$	$(a\vee b)(\neg a\vee \neg b)$
at most one of $x_1..x_k$	prefix variables $p_i$: $x_i\Rightarrow p_i$, $p_{i-1}\Rightarrow p_i$, $p_{i-1}\Rightarrow \neg x_i$ ($O(k)$ clauses instead of $O(k^2)$)
exactly one of $x_1..x_k$	at most one + one clause $(x_1\vee \cdots \vee x_k)$ is not 2-SAT unless $k\le 2$

Patterns: two choices per object with pairwise conflicts (labels above/below points, segments left/right), “binary search the answer, then 2-SAT feasibility”, 2-colouring with extra implications. For many conflicts from geometry or ranges, add edges to segment-tree nodes of literals instead of $O(k^2)$ pairs.

Proof: the 2-SAT criterion and assignment rule

The implication graph is skew-symmetric: $u\to v$ iff $\neg v\to \neg u$. If $x$ and $\neg x$ share an SCC, any assignment must make $x\Rightarrow \neg x$ and $\neg x\Rightarrow x$ true, impossible. Otherwise, with components numbered in topological order, set $x$ true iff $\text{comp}(x)>\text{comp}(\neg x)$. Suppose an implication $u\to v$ is violated: $u$ true, $v$ false. Then $\text{comp}(u)>\text{comp}(\neg u)$ and $\text{comp}(\neg v)>\text{comp}(v)$. The edge $u\to v$ gives $\text{comp}(u)\le \text{comp}(v)$, and its mirror $\neg v\to \neg u$ gives $\text{comp}(\neg v)\le \text{comp}(\neg u)$. Chaining: $\text{comp}(u)\le \text{comp}(v)<\text{comp}(\neg v)\le \text{comp}(\neg u)<\text{comp}(u)$, a contradiction.

Lexicographically smallest satisfying assignment: try $x_i=$ false in order and propagate implications (DFS), undoing on contradiction: $O(nm)$. Counting satisfying assignments of 2-SAT is p-complete.

Incremental SCC

Edges are added in order; for each edge compute the first prefix after which its endpoints are strongly connected. Divide and conquer on time: for a time range $[l,r]$ with its candidate edges, run one SCC on edges with index $\le \text{mid}$ (over DSU-contracted vertices); edges that close by mid go left, the rest right; solve left, contract its merged edges, solve right. $O(m\log m)$ SCC work. Sorting edges by their times and uniting them in a DSU then gives the SCCs of every prefix (Library Checker “Incremental SCC”).

vector<int> incrementalSCC(int n, const vector<pair<int, int>>& E) {   // t[i] in [i, m]; m = never
    int m = sz(E); vector<int> t(m, m), dsu(n); iota(all(dsu), 0);
    auto find = [&](int x) { while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]]; return x; };
    vector<int> id(n, -1);
    auto rec = [&](auto&& self, int l, int r, vector<int>& es) -> void {
        if (es.empty()) return;
        if (l == r) { for (int e : es) t[e] = l; return; }
        int mid = (l + r) / 2; vector<int> vs;
        for (int e : es) for (int x : {find(E[e].first), find(E[e].second)}) if (id[x] < 0) id[x] = sz(vs), vs.push_back(x);
        vector<vector<int>> g(sz(vs));
        for (int e : es) if (e <= mid) g[id[find(E[e].first)]].push_back(id[find(E[e].second)]);
        SCC s(g); vector<int> left, right;
        for (int e : es) (e <= mid && s.comp[id[find(E[e].first)]] == s.comp[id[find(E[e].second)]] ? left : right).push_back(e);
        for (int x : vs) id[x] = -1;
        self(self, l, mid, left);
        for (int e : left) { int a = find(E[e].first), b = find(E[e].second); if (a != b) dsu[a] = b; }
        self(self, mid + 1, r, right);
    };
    vector<int> es(m); iota(es.begin(), es.end(), 0);
    rec(rec, 0, m, es);
    return t;
}

Proof sketch: the divide and conquer on time

Invariant: when solving $[l,r]$ with candidate set $S$, all edges with time $<l$ are contracted in the DSU, every edge in $S$ has time in $[l,r]$, and edges not in $S$ with index $\le r$ have time $<l$ (contracted) or $>r$; the latter lie on no cycle within the prefix $r$ (otherwise they’d have time $\le r$), so they don’t affect SCCs of prefixes in $[l,r]$ and can be dropped. Running SCC on the contracted graph with edges of index $\le \text{mid}$ from $S$ therefore yields exactly the SCCs of prefix $\text{mid}$, so an edge’s time is $\le \text{mid}$ iff its endpoints are strongly connected there. Each edge appears in one subproblem per level, $O(\log m)$ levels.

Condensing loses information

A self-loop disappears into its component when contracting — if “can we stay here forever” matters, record self-loops separately before condensing. Contracting can also produce many parallel edges between two components; the dag() helper above deduplicates them, but a hand-rolled version that doesn’t will silently double-count anything sensitive to edge multiplicity.