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)

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)

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

Path that visits every edge exactly once.

// 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.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Advanced Graph Algorithms

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

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​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