Advanced Graph Algorithms

1. Minimum Spanning Trees

A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

  Original Graph:              MST (total weight = 7):

    1 ---2--- 2                  1 ---2--- 2
    |  \      |                  |         |
    4    3    1                  4         1
    |      \  |                  |         |
    3 ---5--- 4                  3         4

Kruskal's Algorithm with Disjoint Set Union (DSU)

Sort all edges by weight, then greedily add edges that do not form a cycle (detected via DSU).

Python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.rank[a] < self.rank[b]:
            a, b = b, a
        self.parent[b] = a
        if self.rank[a] == self.rank[b]:
            self.rank[a] += 1
        return True

def kruskal(n, edges):
    # edges = [(weight, u, v), ...]
    edges.sort()
    dsu = DSU(n)
    mst_weight = 0
    mst_edges = []
    for w, u, v in edges:
        if dsu.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break
    return mst_weight, mst_edges

C++
struct DSU {
    vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

long long kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long mst = 0;
    int cnt = 0;
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            mst += w;
            if (++cnt == n - 1) break;
        }
    }
    return mst;
}

Prim's Algorithm

Grow the MST from a single vertex, always adding the cheapest edge that connects a new vertex to the current tree. Uses a priority queue.

Python
import heapq

def prim(n, adj):
    # adj[u] = [(weight, v), ...]
    visited = [False] * n
    heap = [(0, 0)]  # (weight, vertex)
    mst_weight = 0
    edges_used = 0
    while heap and edges_used < n:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_weight += w
        edges_used += 1
        for wt, v in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (wt, v))
    return mst_weight

C++
long long prim(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> vis(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});
    long long mst = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        mst += w;
        for (auto& [wt, v] : adj[u])
            if (!vis[v]) pq.push({wt, v});
    }
    return mst;
}

2. Bridges & Articulation Points

A bridge is an edge whose removal disconnects the graph. An articulation point is a vertex whose removal (along with its edges) disconnects the graph. Both are found using Tarjan's algorithm in a single DFS.

    1 --- 2 --- 3          Bridges: (2,3), (3,4)
    |   / |     |          Articulation Points: 2, 3
    |  /  |     |
    4     5     6
              / |
             7  8

  Edge (2,3) is a bridge: removing it disconnects {1,2,4,5} from {3,6,7,8}

Python
def find_bridges_and_aps(n, adj):
    disc = [-1] * n
    low = [0] * n
    parent = [-1] * n
    bridges = []
    aps = set()
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in adj[u]:
            if disc[v] == -1:
                children += 1
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
                # Bridge check
                if low[v] > disc[u]:
                    bridges.append((u, v))
                # AP check
                if parent[u] == -1 and children > 1:
                    aps.add(u)
                if parent[u] != -1 and low[v] >= disc[u]:
                    aps.add(u)
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return bridges, aps

C++
int timer_ = 0;
vector<int> disc, low, par;
vector<pair<int,int>> bridges;
set<int> aps;

void dfs(int u, vector<vector<int>>& adj) {
    disc[u] = low[u] = timer_++;
    int children = 0;
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            children++;
            par[v] = u;
            dfs(v, adj);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u])
                bridges.push_back({u, v});
            if (par[u] == -1 && children > 1)
                aps.insert(u);
            if (par[u] != -1 && low[v] >= disc[u])
                aps.insert(u);
        } else if (v != par[u]) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

3. Strongly Connected Components

An SCC is a maximal set of vertices such that every vertex is reachable from every other vertex in the set (in a directed graph).

  Directed Graph:                    Condensation (DAG):

    1 --> 2 --> 3                    {1,2,4} --> {3,5} --> {6}
    ^    /      |
    |  /        v
    4           5 --> 6

  SCC 1: {1, 2, 4}   SCC 2: {3, 5}   SCC 3: {6}

Kosaraju's Algorithm

Two-pass DFS: (1) DFS on original graph, record finish order. (2) DFS on reversed graph in reverse finish order. Each DFS tree in pass 2 is an SCC.

Python
def kosaraju(n, adj):
    # Pass 1: DFS on original graph, record finish order
    visited = [False] * n
    order = []

    def dfs1(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

    for i in range(n):
        if not visited[i]:
            dfs1(i)

    # Build reversed graph
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    # Pass 2: DFS on reversed graph in reverse finish order
    visited = [False] * n
    sccs = []

    def dfs2(u, comp):
        visited[u] = True
        comp.append(u)
        for v in radj[u]:
            if not visited[v]:
                dfs2(v, comp)

    for u in reversed(order):
        if not visited[u]:
            comp = []
            dfs2(u, comp)
            sccs.append(comp)
    return sccs

Tarjan's SCC Algorithm

Single-pass DFS using a stack. Maintains disc and low values. When low[u] == disc[u], pop the stack to get the SCC.

C++
int timer_ = 0, nscc = 0;
vector<int> disc, low, comp, stk;
vector<bool> on_stk;
vector<vector<int>> sccs;

void dfs(int u, vector<vector<int>>& adj) {
    disc[u] = low[u] = timer_++;
    stk.push_back(u);
    on_stk[u] = true;
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            dfs(v, adj);
            low[u] = min(low[u], low[v]);
        } else if (on_stk[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (low[u] == disc[u]) {
        vector<int> scc;
        while (true) {
            int v = stk.back(); stk.pop_back();
            on_stk[v] = false;
            comp[v] = nscc;
            scc.push_back(v);
            if (v == u) break;
        }
        sccs.push_back(scc);
        nscc++;
    }
}

4. Lowest Common Ancestor (LCA)

Given a rooted tree, the LCA of two nodes u and v is the deepest node that is an ancestor of both u and v. LCA is fundamental for tree path queries.

            1
          / | \
         2  3  4
        / \    |
       5   6   7
      / \
     8   9

  LCA(8, 6) = 2       (2 is the deepest common ancestor)
  LCA(8, 7) = 1       (root is the only common ancestor)
  LCA(5, 9) = 5       (5 is an ancestor of 9... wait, 9's parent is 5)
  LCA(8, 9) = 5       (both are children of 5)

Binary Lifting

Precompute up[v][k] = the 2^k-th ancestor of v. To find LCA(u, v): first equalize depths, then lift both nodes simultaneously until they meet.

Python
import math

class LCABinaryLifting:
    def __init__(self, n, adj, root=0):
        self.LOG = max(1, math.ceil(math.log2(n)))
        self.depth = [0] * n
        self.up = [[-1] * n for _ in range(self.LOG + 1)]

        # BFS to compute depth and immediate parent
        from collections import deque
        q = deque([root])
        visited = [False] * n
        visited[root] = True
        self.up[0][root] = root
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    self.depth[v] = self.depth[u] + 1
                    self.up[0][v] = u
                    q.append(v)

        # Fill binary lifting table
        for k in range(1, self.LOG + 1):
            for v in range(n):
                self.up[k][v] = self.up[k-1][self.up[k-1][v]]

    def query(self, u, v):
        # Make u the deeper node
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        diff = self.depth[u] - self.depth[v]

        # Lift u to same depth as v
        for k in range(self.LOG + 1):
            if (diff >> k) & 1:
                u = self.up[k][u]

        if u == v:
            return u

        # Lift both until they converge
        for k in range(self.LOG, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]
        return self.up[0][u]

C++
const int MAXN = 200005, LOG = 18;
int up[LOG][MAXN], depth_[MAXN];
vector<int> adj[MAXN];

void bfs(int root, int n) {
    memset(depth_, -1, sizeof(depth_));
    queue<int> q;
    q.push(root);
    depth_[root] = 0;
    up[0][root] = root;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (depth_[v] == -1) {
                depth_[v] = depth_[u] + 1;
                up[0][v] = u;
                q.push(v);
            }
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 0; v < n; v++)
            up[k][v] = up[k-1][up[k-1][v]];
}

int lca(int u, int v) {
    if (depth_[u] < depth_[v]) swap(u, v);
    int diff = depth_[u] - depth_[v];
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    return up[0][u];
}

Euler Tour + Sparse Table (O(1) Queries)

Reduce LCA to Range Minimum Query (RMQ). Build an Euler tour recording (depth, node) at each step. LCA(u, v) = node with minimum depth between the first occurrences of u and v in the Euler tour. Use a sparse table for O(1) RMQ.

Python
import math

class LCAEulerTour:
    def __init__(self, n, adj, root=0):
        self.euler = []       # (depth, node) at each step
        self.first = [-1] * n  # first occurrence of node in euler
        self.depth = [0] * n

        # Iterative DFS for Euler tour
        stack = [(root, -1, False)]
        while stack:
            u, par, returning = stack.pop()
            self.euler.append((self.depth[u], u))
            if self.first[u] == -1:
                self.first[u] = len(self.euler) - 1
            if not returning:
                for v in reversed(adj[u]):
                    if v != par:
                        self.depth[v] = self.depth[u] + 1
                        stack.append((u, par, True))  # return to u after v
                        stack.append((v, u, False))
                        break

        # Build sparse table on euler array
        m = len(self.euler)
        self.LOG = max(1, int(math.log2(m))) + 1
        self.sparse = [None] * self.LOG
        self.sparse[0] = self.euler[:]
        for k in range(1, self.LOG):
            length = 1 << k
            self.sparse[k] = []
            for i in range(m - length + 1):
                self.sparse[k].append(
                    min(self.sparse[k-1][i],
                        self.sparse[k-1][i + (1 << (k-1))])
                )

    def query(self, u, v):
        l = self.first[u]
        r = self.first[v]
        if l > r:
            l, r = r, l
        k = int(math.log2(r - l + 1))
        result = min(self.sparse[k][l], self.sparse[k][r - (1 << k) + 1])
        return result[1]  # return the node

Path Queries Using LCA

Many tree problems reduce to path queries. With LCA + prefix sums on the tree:

  Tree with values on nodes:

        (3) 1              prefix[1] = 3
        / \                prefix[2] = 5, prefix[3] = 7
     (2)2  (4)3            prefix[4] = 6, prefix[5] = 8
      / \
   (1)4  (3)5

  path_sum(4, 5) = prefix[4] + prefix[5] - 2*prefix[LCA(4,5)] + value[LCA(4,5)]
                 = 6 + 8 - 2*5 + 2  =  6
                 = value[4] + value[2] + value[5]  =  1 + 2 + 3  =  6  ✓

5. Maximum Flow

Given a directed graph with edge capacities, a source s, and a sink t, find the maximum amount of flow that can be pushed from s to t.

         10       10
    s --------> A --------> t
    |           ^           ^
    |  10       |  5        |  10
    v           |           |
    B --------> C --------> D
         15          10

  Max flow = 20 (push 10 via s->A->t, and 10 via s->B->C->D->t)

Ford-Fulkerson Method

Repeatedly find an augmenting path from s to t in the residual graph and push flow along it. The residual graph includes reverse edges to allow "undoing" flow.

Edmonds-Karp (BFS-based Ford-Fulkerson)

Use BFS to find the shortest augmenting path. This guarantees O(VE^2) time.

Python
from collections import deque

def edmonds_karp(n, adj, cap, s, t):
    # adj[u] = list of neighbors (including reverse edges)
    # cap = 2D capacity matrix, cap[u][v] = remaining capacity
    def bfs():
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if parent[v] == -1 and cap[u][v] > 0:
                    parent[v] = u
                    if v == t:
                        return parent
                    q.append(v)
        return None

    flow = 0
    while True:
        parent = bfs()
        if parent is None:
            break
        # Find bottleneck
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, cap[u][v])
            v = u
        # Update residual capacities
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= path_flow
            cap[v][u] += path_flow
            v = u
        flow += path_flow
    return flow

Dinic's Algorithm

The gold standard for max flow in competitive programming. Uses BFS to build level graphs, then DFS with blocking flow. Achieves O(V^2 * E) in general, O(E * sqrt(V)) for unit-capacity graphs.

C++
struct Dinic {
    struct Edge { int to, rev; long long cap; };
    vector<vector<Edge>> graph;
    vector<int> level, iter_;
    int n;

    Dinic(int n) : n(n), graph(n), level(n), iter_(n) {}

    void add_edge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto& e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int& i = iter_[v]; i < (int)graph[v].size(); i++) {
            Edge& e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(iter_.begin(), iter_.end(), 0);
            long long d;
            while ((d = dfs(s, t, LLONG_MAX)) > 0)
                flow += d;
        }
        return flow;
    }
};

6. Bipartite Matching

Given a bipartite graph with left vertices L and right vertices R, find the maximum number of edges such that no vertex appears more than once.

  L    R          Maximum Matching (bold):
  1 -- a          1 == a
  1 -- b          2 == b
  2 -- b          3 == c
  2 -- c
  3 -- c          Size = 3
  3 -- a

Kuhn's Algorithm (Hungarian-style DFS)

For each left vertex, try to find an augmenting path via DFS. If the right vertex is free, match it. If not, try to re-match the current occupant.

Python
def max_matching(n_left, n_right, adj):
    # adj[u] = list of right vertices that left vertex u connects to
    match_right = [-1] * n_right

    def dfs(u, visited):
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or dfs(match_right[v], visited):
                    match_right[v] = u
                    return True
        return False

    result = 0
    for u in range(n_left):
        visited = [False] * n_right
        if dfs(u, visited):
            result += 1
    return result

Hopcroft-Karp Algorithm

Finds augmenting paths in phases using BFS (to find shortest augmenting paths) then DFS (to find a maximal set of vertex-disjoint augmenting paths). Each phase increases matching by at least 1 and there are at most O(sqrt(V)) phases.

C++
struct HopcroftKarp {
    int n, m;
    vector<vector<int>> adj;
    vector<int> matchL, matchR, dist;

    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1), dist(n) {}

    void add_edge(int u, int v) { adj[u].push_back(v); }

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INT_MAX;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w == -1) {
                    found = true;
                } else if (dist[w] == INT_MAX) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int w = matchR[v];
            if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }

    int solve() {
        int ans = 0;
        while (bfs())
            for (int u = 0; u < n; u++)
                if (matchL[u] == -1 && dfs(u))
                    ans++;
        return ans;
    }
};

7. Bellman-Ford

Single-source shortest path algorithm that handles negative edge weights. Can also detect negative-weight cycles.

      A --(-5)--> B
      |           ^
      1           |
      v           |
      C ---2------+

  From A: Dijkstra visits C (dist=1), then B via C (dist=3).
  But the correct shortest path is A->B with dist=-5.
  Dijkstra never revisits A->B because it greedily finalized B=3.

Python
def bellman_ford(n, edges, src):
    # edges = [(u, v, w), ...]
    dist = [float('inf')] * n
    dist[src] = 0

    # Relax all edges V-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycles (V-th relaxation)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle detected

    return dist

C++
const long long INF = 1e18;

vector<long long> bellman_ford(int n, vector<tuple<int,int,long long>>& edges, int src) {
    vector<long long> dist(n, INF);
    dist[src] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Detect negative cycle
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return {};  // negative cycle
        }
    }
    return dist;
}

8. Floyd-Warshall

All-pairs shortest path in O(V^3). Elegantly simple: try every vertex as an intermediate node.

Python
def floyd_warshall(n, dist):
    # dist[i][j] = weight of edge i->j, or float('inf') if no edge
    # dist[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

C++
const long long INF = 1e18;

void floyd_warshall(int n, vector<vector<long long>>& dist) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

Transitive Closure

Determine which vertices can reach which. Replace + with OR and min with OR:

Python
def transitive_closure(n, reachable):
    # reachable[i][j] = True if edge from i to j exists
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reachable[i][j] = reachable[i][j] or (reachable[i][k] and reachable[k][j])
    return reachable

9. Euler Paths & Circuits

An Euler path visits every edge exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Hierholzer's Algorithm

Efficiently finds an Euler path/circuit in O(E) time by walking along unused edges and splicing in sub-tours.

Python
from collections import defaultdict

def hierholzer(edges, directed=True):
    # Build adjacency list with edge indices for removal
    adj = defaultdict(list)
    if directed:
        for u, v in edges:
            adj[u].append(v)
    else:
        for i, (u, v) in enumerate(edges):
            adj[u].append((v, i))
            adj[v].append((u, i))

    # Find start vertex
    if directed:
        start = edges[0][0]
        # Prefer vertex with out-degree > in-degree
        in_deg = defaultdict(int)
        out_deg = defaultdict(int)
        for u, v in edges:
            out_deg[u] += 1
            in_deg[v] += 1
        for node in out_deg:
            if out_deg[node] - in_deg[node] == 1:
                start = node
                break
    else:
        start = edges[0][0]
        for node in adj:
            if len(adj[node]) % 2 == 1:
                start = node
                break

    # Hierholzer's
    stack = [start]
    circuit = []
    if directed:
        while stack:
            v = stack[-1]
            if adj[v]:
                u = adj[v].pop()
                stack.append(u)
            else:
                circuit.append(stack.pop())
    else:
        used = [False] * len(edges)
        while stack:
            v = stack[-1]
            while adj[v] and used[adj[v][-1][1]]:
                adj[v].pop()
            if adj[v]:
                u, idx = adj[v].pop()
                used[idx] = True
                stack.append(u)
            else:
                circuit.append(stack.pop())

    circuit.reverse()
    return circuit

C++
// Directed Euler path/circuit using Hierholzer's
vector<int> hierholzer(int start, vector<vector<int>>& adj) {
    stack<int> stk;
    vector<int> circuit;
    stk.push(start);
    while (!stk.empty()) {
        int v = stk.top();
        if (!adj[v].empty()) {
            int u = adj[v].back();
            adj[v].pop_back();
            stk.push(u);
        } else {
            circuit.push_back(v);
            stk.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

10. 2-SAT

Given a boolean formula in 2-CNF (each clause has exactly 2 literals), determine if there is a satisfying assignment. Solved in O(V + E) using SCCs on the implication graph.

  Formula: (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)

  Implication graph edges:
    NOT x1 => x2,   NOT x2 => x1    (from clause 1)
    x1 => x3,       NOT x3 => NOT x1 (from clause 2)
    x2 => NOT x3,   x3 => NOT x2     (from clause 3)

  Solution: x1=true, x2=false, x3=true

Python
class TwoSAT:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(2 * n)]

    def add_clause(self, u, neg_u, v, neg_v):
        # clause: (u if not neg_u, else NOT u) OR (v if not neg_v, else NOT v)
        a = 2 * u + neg_u
        b = 2 * v + neg_v
        self.adj[a ^ 1].append(b)  # NOT a => b
        self.adj[b ^ 1].append(a)  # NOT b => a

    def solve(self):
        N = 2 * self.n
        order = []
        comp = [-1] * N
        visited = [False] * N

        def dfs1(v):
            visited[v] = True
            for u in self.adj[v]:
                if not visited[u]:
                    dfs1(u)
            order.append(v)

        # Build reverse graph
        radj = [[] for _ in range(N)]
        for v in range(N):
            for u in self.adj[v]:
                radj[u].append(v)

        def dfs2(v, c):
            comp[v] = c
            for u in radj[v]:
                if comp[u] == -1:
                    dfs2(u, c)

        for v in range(N):
            if not visited[v]:
                dfs1(v)

        c = 0
        for v in reversed(order):
            if comp[v] == -1:
                dfs2(v, c)
                c += 1

        # Check satisfiability
        for i in range(self.n):
            if comp[2 * i] == comp[2 * i + 1]:
                return None  # unsatisfiable

        # Extract assignment
        assignment = [False] * self.n
        for i in range(self.n):
            assignment[i] = comp[2 * i] > comp[2 * i + 1]
        return assignment

C++
struct TwoSAT {
    int n;
    vector<vector<int>> adj, radj;
    vector<int> order, comp;
    vector<bool> vis;

    TwoSAT(int n) : n(n), adj(2*n), radj(2*n), comp(2*n, -1), vis(2*n, false) {}

    // (u, neg_u) OR (v, neg_v)
    void add_clause(int u, bool nu, int v, bool nv) {
        int a = 2*u + nu, b = 2*v + nv;
        adj[a^1].push_back(b);
        radj[b].push_back(a^1);
        adj[b^1].push_back(a);
        radj[a].push_back(b^1);
    }

    void dfs1(int v) {
        vis[v] = true;
        for (int u : adj[v]) if (!vis[u]) dfs1(u);
        order.push_back(v);
    }

    void dfs2(int v, int c) {
        comp[v] = c;
        for (int u : radj[v]) if (comp[u] == -1) dfs2(u, c);
    }

    bool solve(vector<bool>& result) {
        for (int v = 0; v < 2*n; v++)
            if (!vis[v]) dfs1(v);
        int c = 0;
        for (int i = 2*n - 1; i >= 0; i--)
            if (comp[order[i]] == -1) dfs2(order[i], c++);
        result.resize(n);
        for (int i = 0; i < n; i++) {
            if (comp[2*i] == comp[2*i+1]) return false;
            result[i] = comp[2*i] > comp[2*i+1];
        }
        return true;
    }
};

11. Centroid Decomposition

A divide-and-conquer technique on trees. The centroid of a tree is a vertex whose removal results in no subtree with more than N/2 vertices. Recursively decompose the tree by finding and removing centroids.

  Original tree:           Centroid decomposition tree:
       1                          3
      / \                       / | \
     2   3                     1  5  6
    /   / \                    |
   4   5   6                   2
  /                            |
 7                             4
                               |
                               7

  Centroid of original tree: 3 (removing 3 gives subtrees of size <= 3)
  Depth of centroid tree: O(log N)

Python
import sys
sys.setrecursionlimit(300000)

class CentroidDecomposition:
    def __init__(self, n, adj):
        self.n = n
        self.adj = adj
        self.sub_size = [0] * n
        self.removed = [False] * n
        self.centroid_parent = [-1] * n
        self.root = self._build(0, n)

    def _get_subtree_size(self, v, p):
        self.sub_size[v] = 1
        for u in self.adj[v]:
            if u != p and not self.removed[u]:
                self._get_subtree_size(u, v)
                self.sub_size[v] += self.sub_size[u]
        return self.sub_size[v]

    def _get_centroid(self, v, p, tree_size):
        for u in self.adj[v]:
            if u != p and not self.removed[u] and self.sub_size[u] > tree_size // 2:
                return self._get_centroid(u, v, tree_size)
        return v

    def _build(self, v, size_hint):
        tree_size = self._get_subtree_size(v, -1)
        centroid = self._get_centroid(v, -1, tree_size)
        self.removed[centroid] = True

        for u in self.adj[centroid]:
            if not self.removed[u]:
                child_centroid = self._build(u, self.sub_size[u])
                self.centroid_parent[child_centroid] = centroid

        return centroid

C++
const int MAXN = 200005;
vector<int> adj[MAXN];
int sub_sz[MAXN], cpar[MAXN];
bool removed[MAXN];

int get_size(int v, int p) {
    sub_sz[v] = 1;
    for (int u : adj[v])
        if (u != p && !removed[u])
            sub_sz[v] += get_size(u, v);
    return sub_sz[v];
}

int get_centroid(int v, int p, int tsz) {
    for (int u : adj[v])
        if (u != p && !removed[u] && sub_sz[u] > tsz / 2)
            return get_centroid(u, v, tsz);
    return v;
}

void build(int v, int par) {
    int tsz = get_size(v, -1);
    int c = get_centroid(v, -1, tsz);
    removed[c] = true;
    cpar[c] = par;

    for (int u : adj[c])
        if (!removed[u])
            build(u, c);
}

12. Practice Problems