Advanced Graph Algorithms

Beyond Basic Graphs

Once you’ve mastered BFS, DFS, and shortest paths, it’s time for advanced graph techniques. These algorithms appear in harder CF problems (1700+) and ICPC regionals.

Pattern Recognition Signals:

“Strongly connected” → SCC (Kosaraju/Tarjan)
“Bridge/cut vertex” → Bridge finding algorithm
“Boolean satisfiability” → 2-SAT
“Bipartite matching” → Hungarian/Kuhn’s algorithm
“Maximum flow” → Ford-Fulkerson/Dinic

Strongly Connected Components (SCC)

An SCC is a maximal set of vertices where every vertex is reachable from every other. Intuition: In a directed graph, SCCs are “clusters” where you can get from any node to any other within the cluster. The graph of SCCs forms a DAG (no cycles possible, since any cycle would merge SCCs). Why it matters:

Simplify complex graphs by collapsing SCCs to single nodes (condensation)
Solve 2-SAT problems
Analyze dependencies and reachability

Kosaraju’s Algorithm

The Insight: If we process nodes in order of decreasing finish time from a DFS, and run DFS on the reversed graph, each DFS tree corresponds to an SCC. Why does reversing work? In the original graph, if there’s a path from SCC A to SCC B, then in the reversed graph there’s a path from B to A. By processing in finish-time order, we ensure we start from “sink” SCCs (no outgoing edges to other SCCs), so DFS on reversed graph stays within one SCC. Algorithm:

Run DFS on original graph, recording finish order (node goes on stack when its DFS completes)
Process nodes in reverse finish order, running DFS on reversed graph
Each DFS tree in step 2 is an SCC

class SCC {
public:
    int n, numSCC;
    vector<vector<int>> adj, radj;
    vector<int> order, comp;
    vector<bool> visited;
    
    SCC(int n) : n(n), adj(n), radj(n), comp(n, -1), visited(n, false) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    
    void dfs1(int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) dfs1(v);
        }
        order.push_back(u);
    }
    
    void dfs2(int u, int c) {
        comp[u] = c;
        for (int v : radj[u]) {
            if (comp[v] == -1) dfs2(v, c);
        }
    }
    
    int findSCC() {
        // First DFS to get finishing order
        for (int i = 0; i < n; i++) {
            if (!visited[i]) dfs1(i);
        }
        
        // Second DFS on reverse graph in reverse order
        numSCC = 0;
        for (int i = n - 1; i >= 0; i--) {
            int u = order[i];
            if (comp[u] == -1) {
                dfs2(u, numSCC);
                numSCC++;
            }
        }
        
        return numSCC;
    }
    
    // Build condensation graph (DAG of SCCs)
    vector<vector<int>> condensation() {
        vector<set<int>> edges(numSCC);
        for (int u = 0; u < n; u++) {
            for (int v : adj[u]) {
                if (comp[u] != comp[v]) {
                    edges[comp[u]].insert(comp[v]);
                }
            }
        }
        
        vector<vector<int>> dag(numSCC);
        for (int i = 0; i < numSCC; i++) {
            for (int j : edges[i]) {
                dag[i].push_back(j);
            }
        }
        return dag;
    }
};

Tarjan’s Algorithm

Single DFS, more efficient in practice. Key Concepts:

disc[u]: Discovery time of node u (when we first visit it)
low[u]: Lowest discovery time reachable from u’s subtree via tree edges and at most one back edge
onStack: Whether node is in the current DFS path (potential SCC members)

When is u the root of an SCC? When low[u] == disc[u]. This means no node in u’s subtree can reach anything discovered before u, so u and everything on the stack down to u form an SCC. Visual Example:

Graph: 1 → 2 → 3 → 1 (cycle), 3 → 4

DFS from 1:
- Visit 1: disc[1]=0, low[1]=0, push 1
- Visit 2: disc[2]=1, low[2]=1, push 2  
- Visit 3: disc[3]=2, low[3]=2, push 3
- 3→1: 1 is on stack, low[3] = min(low[3], disc[1]) = 0
- Back to 2: low[2] = min(low[2], low[3]) = 0
- Back to 1: low[1] = min(low[1], low[2]) = 0
- low[1]==disc[1]=0, pop until 1: SCC = {1,2,3}
- Visit 4: disc[4]=3, low[4]=3, push 4
- low[4]==disc[4], pop: SCC = {4}

Result: 2 SCCs: {1,2,3} and {4}

class TarjanSCC {
public:
    int n, numSCC, timer;
    vector<vector<int>> adj;
    vector<int> disc, low, comp;
    vector<bool> onStack;
    stack<int> st;
    
    TarjanSCC(int n) : n(n), adj(n), disc(n, -1), low(n), 
                       comp(n, -1), onStack(n, false), numSCC(0), timer(0) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    void dfs(int u) {
        disc[u] = low[u] = timer++;
        st.push(u);
        onStack[u] = true;
        
        for (int v : adj[u]) {
            if (disc[v] == -1) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }
        
        if (low[u] == disc[u]) {
            while (true) {
                int v = st.top();
                st.pop();
                onStack[v] = false;
                comp[v] = numSCC;
                if (v == u) break;
            }
            numSCC++;
        }
    }
    
    int findSCC() {
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) dfs(i);
        }
        return numSCC;
    }
};

Bridges and Articulation Points

Finding Bridges

An edge is a bridge if removing it disconnects the graph. Key Insight: Edge (u, v) where u is the parent of v in DFS tree is a bridge if and only if low[v] > disc[u]. This means v cannot reach u or any ancestor of u through any path other than (u, v). Why low[v] > disc[u] and not >=?

If low[v] == disc[u], v can reach u through another path (a back edge from v’s subtree to u)
Such a back edge would give us an alternative path, so (u, v) wouldn’t be a bridge

Visual Example:

1 - 2 - 3
    |   |
    4 - 5

DFS tree (starting at 1):
1 → 2 → 3 → 5 → 4 (back edge 4-2)

disc: [0, 1, 2, 3, 4] (for nodes 1-5)
low:  [0, 1, 1, 1, 1] (after processing)

Edge 1-2: low[2]=1, disc[1]=0 → low[2] > disc[1] → BRIDGE!
Edge 2-3: low[3]=1, disc[2]=1 → low[3] = disc[2] → not a bridge (cycle through 4-5)

Handling Parallel Edges: We track edge IDs, not just parent nodes, to correctly handle multiple edges between same vertices.

class Bridges {
public:
    int n, timer;
    vector<vector<pair<int, int>>> adj;  // {neighbor, edge_id}
    vector<int> disc, low;
    vector<bool> isBridge;
    
    Bridges(int n, int m) : n(n), adj(n), disc(n, -1), low(n), 
                            isBridge(m, false), timer(0) {}
    
    void addEdge(int u, int v, int id) {
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
    }
    
    void dfs(int u, int parentEdge) {
        disc[u] = low[u] = timer++;
        
        for (auto [v, edgeId] : adj[u]) {
            if (edgeId == parentEdge) continue;
            
            if (disc[v] == -1) {
                dfs(v, edgeId);
                low[u] = min(low[u], low[v]);
                
                if (low[v] > disc[u]) {
                    isBridge[edgeId] = true;
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }
    
    vector<int> findBridges() {
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) dfs(i, -1);
        }
        
        vector<int> bridges;
        for (int i = 0; i < isBridge.size(); i++) {
            if (isBridge[i]) bridges.push_back(i);
        }
        return bridges;
    }
};

Finding Articulation Points

A vertex is an articulation point if removing it disconnects the graph. Two Cases:

Root of DFS tree: u is an AP iff it has 2+ children in the DFS tree. If root has only one child, removing root leaves one connected component.
Non-root node: u is an AP iff some child v has low[v] >= disc[u]. This means v (and its subtree) cannot reach any ancestor of u—so removing u would disconnect v’s subtree.

Why >= for APs but > for bridges?

For bridges: we’re removing an edge, so even if v can reach u via another path, the graph stays connected
For APs: we’re removing vertex u itself, so even if v can reach exactly u (low[v] = disc[u]) via a back edge, that doesn’t help—u is still gone!

Visual Example:

    1
   / \
  2   3
     / \
    4 - 5

Node 1: Root with 2 children → AP (removing 1 splits into {2} and {3,4,5})
Node 3: low[4] = disc[3] (4 can reach 3 via 5-3) → AP? Let's check...
        Actually low[4] < disc[3] because 4-5 and 5-3 forms a cycle.
        So 3 is NOT an AP in this graph.

class ArticulationPoints {
public:
    int n, timer;
    vector<vector<int>> adj;
    vector<int> disc, low;
    vector<bool> isAP;
    
    ArticulationPoints(int n) : n(n), adj(n), disc(n, -1), 
                                 low(n), isAP(n, false), timer(0) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        int children = 0;
        
        for (int v : adj[u]) {
            if (disc[v] == -1) {
                children++;
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                
                // u is AP if:
                // 1. u is root and has 2+ children
                // 2. u is not root and low[v] >= disc[u]
                if (parent == -1 && children > 1) isAP[u] = true;
                if (parent != -1 && low[v] >= disc[u]) isAP[u] = true;
            } else if (v != parent) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }
    
    vector<int> findAPs() {
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) dfs(i, -1);
        }
        
        vector<int> aps;
        for (int i = 0; i < n; i++) {
            if (isAP[i]) aps.push_back(i);
        }
        return aps;
    }
};

2-SAT

Solve boolean satisfiability with clauses of form (x OR y). The Problem: Given n boolean variables and m clauses of form “(a OR b)”, find an assignment that satisfies all clauses, or report impossibility. The Key Transformation: Each clause

(a \lor b)

is equivalent to two implications:

$\neg a \Rightarrow b$ (if a is false, b must be true)
$\neg b \Rightarrow a$ (if b is false, a must be true)

Building the Implication Graph:

Create 2n nodes: for each variable x, one node for x=true and one for x=false
For clause (a OR b): add edges (NOT a → b) and (NOT b → a)

Why SCC? If x and NOT x are in the same SCC, they imply each other:

x ⇒ … ⇒ NOT x ⇒ … ⇒ x
This means x ⇔ NOT x, which is a contradiction!

Finding the Assignment:

Find all SCCs using Tarjan/Kosaraju
If any variable has both states in same SCC → UNSATISFIABLE
Otherwise: in topological order of SCCs, assign TRUE to variables whose TRUE-node comes after FALSE-node (later in topo order = “stronger”)

Common Clause Patterns:

Statement	Clause	Edges to Add
At least one of a, b	(a ∨ b)	¬a→b, ¬b→a
At most one of a, b	(¬a ∨ ¬b)	a→¬b, b→¬a
Exactly one of a, b	Both above	All 4 edges
a must be true	(a ∨ a)	¬a→a
a implies b	(a ⇒ b)	a→b, ¬b→¬a

class TwoSAT {
public:
    int n;  // Number of variables (0 to n-1)
    SCC scc;
    
    TwoSAT(int n) : n(n), scc(2 * n) {}
    
    // Variable x: true = 2*x, false = 2*x+1
    int var(int x, bool val) { return 2 * x + (val ? 0 : 1); }
    int neg(int x) { return x ^ 1; }
    
    // Add clause: (a OR b)
    // Equivalent to: (NOT a => b) AND (NOT b => a)
    void addClause(int a, bool valA, int b, bool valB) {
        int u = var(a, valA);
        int v = var(b, valB);
        scc.addEdge(neg(u), v);
        scc.addEdge(neg(v), u);
    }
    
    // Add implication: a => b
    void addImplication(int a, bool valA, int b, bool valB) {
        int u = var(a, valA);
        int v = var(b, valB);
        scc.addEdge(u, v);
        scc.addEdge(neg(v), neg(u));
    }
    
    // Force variable to specific value
    void forceValue(int a, bool val) {
        addClause(a, val, a, val);
    }
    
    // Check satisfiability and get assignment
    pair<bool, vector<bool>> solve() {
        scc.findSCC();
        
        vector<bool> assignment(n);
        
        for (int i = 0; i < n; i++) {
            if (scc.comp[2*i] == scc.comp[2*i+1]) {
                return {false, {}};  // x and NOT x in same SCC
            }
            // Assign true if false-node has smaller component number
            // (topologically later = reachable from true-node)
            assignment[i] = scc.comp[2*i] > scc.comp[2*i+1];
        }
        
        return {true, assignment};
    }
};

2-SAT Example

// Variables: 0, 1, 2
// Clauses: (x0 OR x1), (NOT x1 OR x2), (NOT x0 OR NOT x2)

TwoSAT sat(3);
sat.addClause(0, true, 1, true);      // x0 OR x1
sat.addClause(1, false, 2, true);     // NOT x1 OR x2
sat.addClause(0, false, 2, false);    // NOT x0 OR NOT x2

auto [satisfiable, assignment] = sat.solve();
if (satisfiable) {
    for (int i = 0; i < 3; i++) {
        cout << "x" << i << " = " << assignment[i] << "\n";
    }
}

Bipartite Matching

Kuhn’s Algorithm (Hungarian)

The Idea: For each left-side node, try to find an augmenting path—a path that alternates between unmatched and matched edges. If we find one, we can “flip” all edges along it, increasing the matching by 1. The DFS greedily tries to match each left node, and if a right node is already matched, it recursively tries to re-match the current partner elsewhere. Complexity: O(V * E) in the worst case. For dense bipartite graphs, Hopcroft-Karp is faster at O(E * sqrt(V)), but Kuhn is simpler and usually sufficient for CP.

class BipartiteMatching {
public:
    int n, m;  // Left side: n vertices, Right side: m vertices
    vector<vector<int>> adj;
    vector<int> match;
    vector<bool> used;
    
    BipartiteMatching(int n, int m) : n(n), m(m), adj(n), match(m, -1) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    bool dfs(int u) {
        for (int v : adj[u]) {
            if (!used[v]) {
                used[v] = true;
                if (match[v] == -1 || dfs(match[v])) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    
    int maxMatching() {
        int result = 0;
        for (int u = 0; u < n; u++) {
            used.assign(m, false);
            if (dfs(u)) result++;
        }
        return result;
    }
    
    vector<pair<int, int>> getMatching() {
        vector<pair<int, int>> matching;
        for (int v = 0; v < m; v++) {
            if (match[v] != -1) {
                matching.push_back({match[v], v});
            }
        }
        return matching;
    }
};

Maximum Flow (Dinic’s Algorithm)

The Problem: Given a directed graph with edge capacities, find the maximum flow from source s to sink t. Why Dinic over Ford-Fulkerson? Ford-Fulkerson with DFS can take O(V * E^2) or even fail to terminate with irrational capacities. Dinic uses BFS to build level graphs and DFS to find blocking flows, achieving O(V^2 * E) in general and O(E * sqrt(V)) on unit-capacity graphs. For bipartite matching, Dinic with max-flow is often as fast as Hopcroft-Karp. When to use max flow: Anytime you see “maximum number of edge-disjoint paths,” “minimum cut,” or “maximum matching in general graphs.” The max-flow min-cut theorem says the maximum flow equals the minimum cut—this duality is incredibly useful.

struct Dinic {
    struct Edge {
        int to, rev;
        ll cap;
    };
    
    int n;
    vector<vector<Edge>> adj;
    vector<int> level, iter;
    
    Dinic(int n) : n(n), adj(n), level(n), iter(n) {}
    
    void addEdge(int from, int to, ll cap) {
        adj[from].push_back({to, (int)adj[to].size(), cap});
        adj[to].push_back({from, (int)adj[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 u = q.front();
            q.pop();
            for (auto& e : adj[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        
        return level[t] >= 0;
    }
    
    ll dfs(int u, int t, ll f) {
        if (u == t) return f;
        
        for (int& i = iter[u]; i < adj[u].size(); i++) {
            Edge& e = adj[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    adj[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        
        return 0;
    }
    
    ll maxFlow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            ll f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

Eulerian Path/Circuit

A path that visits every edge exactly once (contrast with Hamiltonian path, which visits every vertex exactly once—an NP-complete problem). Analogy: The classic “Seven Bridges of Konigsberg” problem. Euler proved in 1736 that you cannot cross all seven bridges exactly once and return to the start — because four landmasses had odd degree. This was the birth of graph theory. Existence conditions (for undirected graphs):

Eulerian circuit (returns to start): all vertices have even degree, and the graph is connected
Eulerian path (start != end): exactly 2 vertices have odd degree (those are the start and end), and the graph is connected
Neither exists: more than 2 vertices have odd degree

For directed graphs: circuit exists if all vertices have in-degree = out-degree; path exists if at most one vertex has out-degree - in-degree = 1 (start) and at most one has in-degree - out-degree = 1 (end). Edge case: Isolated vertices (degree 0) do not affect Euler path/circuit existence — they simply are not visited. But the “connected” requirement applies to the subgraph induced by vertices with nonzero degree.

// Eulerian circuit exists if: all vertices have even degree
// Eulerian path exists if: exactly 0 or 2 vertices have odd degree

vector<int> eulerianPath(int n, vector<pair<int,int>>& edges) {
    vector<vector<pair<int,int>>> adj(n);  // {neighbor, edge_index}
    vector<bool> used(edges.size(), false);
    vector<int> deg(n, 0);
    
    for (int i = 0; i < edges.size(); i++) {
        auto [u, v] = edges[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        deg[u]++;
        deg[v]++;
    }
    
    // Find start vertex
    int start = 0;
    int oddCount = 0;
    for (int i = 0; i < n; i++) {
        if (deg[i] % 2 == 1) {
            start = i;
            oddCount++;
        }
    }
    
    if (oddCount != 0 && oddCount != 2) return {};  // No Eulerian path
    
    vector<int> path;
    stack<int> st;
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top();
        bool found = false;
        
        while (!adj[u].empty()) {
            auto [v, idx] = adj[u].back();
            adj[u].pop_back();
            
            if (!used[idx]) {
                used[idx] = true;
                st.push(v);
                found = true;
                break;
            }
        }
        
        if (!found) {
            path.push_back(u);
            st.pop();
        }
    }
    
    reverse(path.begin(), path.end());
    return path;
}

Practice Problems

Intermediate (1400-1700)

Problem	Topic	Link
Planets and Kingdoms	SCC	CSES
Giant Pizza	2-SAT	CSES
Coin Collector	SCC + DP	CSES

Advanced (1700-2000)

Problem	Topic	Link
Flight Routes Check	SCC	CSES
Mail Delivery	Eulerian	CSES
School Dance	Bipartite Matching	CSES

Key Takeaways

SCC

Kosaraju or Tarjan for strongly connected components.

Bridges/APs

Use low-link values from DFS tree.

2-SAT

Model as implication graph, solve with SCC.

Max Flow

Dinic’s O(V²E) for general, O(E√V) for bipartite.

Next Up

Back to Overview

Return to the complete course curriculum.

​Advanced Graph Algorithms

​Beyond Basic Graphs

​Strongly Connected Components (SCC)

​Kosaraju’s Algorithm

​Tarjan’s Algorithm

​Bridges and Articulation Points

​Finding Bridges

​Finding Articulation Points

​2-SAT

​2-SAT Example

​Bipartite Matching

​Kuhn’s Algorithm (Hungarian)

​Maximum Flow (Dinic’s Algorithm)

​Eulerian Path/Circuit

​Practice Problems

​Intermediate (1400-1700)

​Advanced (1700-2000)

​Key Takeaways

SCC

Bridges/APs

2-SAT

Max Flow

​Next Up

Back to Overview

Advanced Graph Algorithms

Beyond Basic Graphs

Strongly Connected Components (SCC)

Kosaraju’s Algorithm

Tarjan’s Algorithm

Bridges and Articulation Points

Finding Bridges

Finding Articulation Points

2-SAT

2-SAT Example

Bipartite Matching

Kuhn’s Algorithm (Hungarian)

Maximum Flow (Dinic’s Algorithm)

Eulerian Path/Circuit

Practice Problems

Intermediate (1400-1700)

Advanced (1700-2000)

Key Takeaways

Next Up