Advanced Graph Algorithms

📋 At a Glance

Aspect	Details
Time to Read	35 minutes
Prerequisites	Part 11 (Graph Traversal), Part 12 (Shortest Path)
Key Concepts	Strongly Connected Components, Articulation Points, Max Flow, Bipartite Matching
Difficulty	⭐⭐⭐⭐ (Advanced)

┌─────────────────────────────────────────────────────────────────┐
│           ADVANCED GRAPH ALGORITHMS LANDSCAPE                   │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  CONNECTIVITY                    FLOW NETWORKS                  │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │ Strongly        │            │ Maximum Flow    │             │
│  │ Connected       │            │ ─────────────── │             │
│  │ Components      │            │ Ford-Fulkerson  │             │
│  │ ─────────────── │            │ Edmonds-Karp    │             │
│  │ Tarjan's O(V+E) │            │ Push-Relabel    │             │
│  │ Kosaraju's      │            └─────────────────┘             │
│  └─────────────────┘                    │                       │
│          │                              │                       │
│          ▼                              ▼                       │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │ Critical Points │            │ Min Cut         │             │
│  │ ─────────────── │            │ ─────────────── │             │
│  │ Articulation    │            │ Max-Flow =      │             │
│  │ Points          │            │ Min-Cut         │             │
│  │ Bridges         │            │ (Duality)       │             │
│  └─────────────────┘            └─────────────────┘             │
│                                         │                       │
│                                         ▼                       │
│                                 ┌─────────────────┐             │
│                                 │ Bipartite       │             │
│                                 │ Matching        │             │
│                                 │ ─────────────── │             │
│                                 │ Hungarian Alg   │             │
│                                 │ Hopcroft-Karp   │             │
│                                 └─────────────────┘             │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

Find SCCs: Implement Tarjan's and Kosaraju's algorithms
Identify critical points: Find articulation points and bridges
Solve flow problems: Apply Ford-Fulkerson and Edmonds-Karp
Match bipartite graphs: Use Hungarian algorithm for optimal assignment
Apply min-cut: Understand max-flow min-cut duality

🔥 Production Story: The Microservice Dependency Nightmare

A fintech company's platform grew to 200+ microservices. One Monday morning, a seemingly minor deployment caused a cascade failure affecting 40% of the system.

The Incident

08:15 - Payment service deployed new version
08:17 - Order service health checks failing
08:19 - Inventory service unresponsive
08:22 - Customer dashboard showing errors
08:25 - Trading halted, revenue loss: $50K/minute

The team had no visibility into service dependencies. They couldn't answer:

Which services form tightly coupled groups?
Which services, if they fail, would partition the system?
What's the maximum throughput between any two services?

The Investigation

The architect analyzed the call graph:

JAVA(14 lines)
Code
Loading syntax highlighter...

The Solution

They applied advanced graph algorithms:

JAVA(40 lines)
Code
Loading syntax highlighter...

The Impact

Metric	Before	After
Mean Time to Recovery	45 minutes	8 minutes
Cascade failures/month	12	1
Critical services identified	0	23
Deployment confidence	Low	High

The insight: Understanding graph structure transforms reactive firefighting into proactive architecture.

🧠 Mental Model: The City Infrastructure

Think of advanced graph algorithms as city planning tools:

┌─────────────────────────────────────────────────────────────────┐
│                    CITY INFRASTRUCTURE                          │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  STRONGLY CONNECTED              ARTICULATION POINTS            │
│  COMPONENTS                      (Single Points of Failure)     │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │  Downtown       │            │                 │             │
│  │  ┌───┐  ┌───┐   │            │    A ─── B      │             │
│  │  │ A │──│ B │   │            │    │            │             │
│  │  └─┬─┘  └─┬─┘   │            │    ▼            │             │
│  │    │  ╲╱   │    │            │   [C] ◄───────  │  C is       │
│  │    │  ╱╲   │    │            │    │             critical     │
│  │  ┌─┴─┐  ┌─┴─┐   │            │    ▼            │             │
│  │  │ C │──│ D │   │            │    D ─── E      │             │
│  │  └───┘  └───┘   │            │                 │             │
│  │ All reachable   │            └─────────────────┘             │
│  │ from each other │                                            │
│  └─────────────────┘                                            │
│                                                                 │
│  MAX FLOW                        BIPARTITE MATCHING             │
│  (Traffic Capacity)              (Job Assignment)               │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │     8    5      │            │ Workers  Jobs   │             │
│  │  A ───→ B ───→  │            │    A ──── 1     │             │
│  │  │      │    T  │            │    B ──┬─ 2     │             │
│  │  │3     │2      │            │    C ──┘─ 3     │             │
│  │  ▼      ▼       │            │                 │             │
│  │  S ───→ C ───→  │            │ Maximum         │             │
│  │     6    4      │            │ matching = 3    │             │
│  └─────────────────┘            └─────────────────┘             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Key analogies:

SCC = Neighborhoods where you can walk from any point to any other
Articulation Point = The only bridge connecting two parts of city
Max Flow = Maximum traffic the road network can handle
Bipartite Matching = Assigning taxi drivers to passengers optimally

🔬 Deep Dive: Strongly Connected Components

Understanding SCCs

A Strongly Connected Component is a maximal set of vertices where every vertex is reachable from every other vertex.

┌─────────────────────────────────────────────────────────────────┐
│                    SCC VISUALIZATION                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Original Graph:                 SCCs Identified:               │
│                                                                 │
│    1 ──→ 2                        ┌─────────┐                   │
│    ↑     ↓                        │ SCC 1   │                   │
│    └──── 3 ──→ 4                  │ {1,2,3} │──→ {4} ──→ {5,6}  │
│              ↓                    └─────────┘    SCC2    SCC3   │
│         5 ←── 6                                                 │
│         └────→                                                  │
│                                                                 │
│  Within SCC: bidirectional reachability                         │
│  Between SCCs: DAG (no cycles possible)                         │
└─────────────────────────────────────────────────────────────────┘

Kosaraju's Algorithm

Kosaraju's uses two DFS passes - one on original graph, one on reversed:

JAVA(67 lines)
Code
Loading syntax highlighter...

Why it works:

┌─────────────────────────────────────────────────────────────────┐
│                 KOSARAJU'S INTUITION                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Pass 1: Record finish times                                    │
│  ─────────────────────────────                                  │
│  Vertices that finish later can reach more vertices             │
│  (they're "upstream" in the SCC DAG)                            │
│                                                                 │
│     SCC_A ──→ SCC_B ──→ SCC_C                                   │
│       ▲                                                         │
│       │                                                         │
│  Finishes last (can reach B and C)                              │
│                                                                 │
│  Pass 2: DFS on reversed graph                                  │
│  ─────────────────────────────                                  │
│  Starting from highest finish time:                             │
│  - Can only reach vertices in SAME SCC                          │
│  - Reverse edges prevent crossing to other SCCs                 │
│                                                                 │
│     SCC_A ←── SCC_B ←── SCC_C   (reversed)                      │
│       │                                                         │
│       └── Start here, stays in SCC_A                            │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Tarjan's Algorithm

Tarjan's is more elegant - single DFS pass using low-link values:

JAVA(75 lines)
Code
Loading syntax highlighter...

Low-link visualization:

┌─────────────────────────────────────────────────────────────────┐
│                    TARJAN'S LOW-LINK                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Discovery order:  1 → 2 → 3 → 4                                │
│                                                                 │
│    1 ────→ 2                  ids:      1  2  3  4              │
│    ↑       ↓                  lowLinks: 1  1  1  4              │
│    └────── 3 ────→ 4                                            │
│                                                                 │
│  Back edge 3→1 updates lowLinks:                                │
│  - lowLink[3] = min(3, id[1]) = 1                               │
│  - lowLink[2] = min(2, lowLink[3]) = 1                          │
│  - lowLink[1] = min(1, lowLink[2]) = 1                          │
│                                                                 │
│  SCC roots: vertices where id[v] == lowLink[v]                  │
│  - Vertex 1: id=1, lowLink=1 → ROOT of SCC {1,2,3}              │
│  - Vertex 4: id=4, lowLink=4 → ROOT of SCC {4}                  │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Comparison

Aspect	Kosaraju's	Tarjan's
DFS passes	2	1
Extra space	O(V) for reverse graph	O(V) for stack
Simplicity	Easier to understand	More elegant
Constants	Slightly higher	Lower
Output order	Reverse topological	Reverse topological

🔬 Deep Dive: Articulation Points and Bridges

Articulation Points

An articulation point (cut vertex) is a vertex whose removal disconnects the graph.

JAVA(81 lines)
Code
Loading syntax highlighter...

Why the conditions work:

┌─────────────────────────────────────────────────────────────────┐
│              ARTICULATION POINT CONDITIONS                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Condition 1: Root with 2+ children                             │
│  ──────────────────────────────────                             │
│       ┌───┐                                                     │
│       │ R │ ← Root                                              │
│      ╱     ╲                                                    │
│  ┌───┐     ┌───┐                                                │
│  │ A │     │ B │  Two subtrees                                  │
│  └───┘     └───┘                                                │
│                                                                 │
│  If R is removed, A and B are disconnected                      │
│  (children in DFS tree have no other connection)                │
│                                                                 │
│  Condition 2: low[v] >= discovery[u]                            │
│  ───────────────────────────────────                            │
│       1                                                         │
│      ╱│                                                         │
│     2 │    discovery[1]=0, low[1]=0                             │
│    ╱│ │    discovery[2]=1, low[2]=0 (back edge to 1)            │
│   3 │ │    discovery[3]=2, low[3]=2 (no back edge!)             │
│     │ │                                                         │
│     └─┘    low[3] >= discovery[2] → 2 is articulation           │
│            (3 can't reach above 2 without going through 2)      │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Bridges

A bridge is an edge whose removal disconnects the graph:

JAVA(63 lines)
Code
Loading syntax highlighter...

Bridge vs Articulation Point:

┌─────────────────────────────────────────────────────────────────┐
│           BRIDGE vs ARTICULATION POINT                          │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Articulation: low[v] >= discovery[u]                           │
│  Bridge:       low[v] >  discovery[u]                           │
│                                                                 │
│  Example where u is articulation but (u,v) is NOT bridge:       │
│                                                                 │
│      1 ─── 2                                                    │
│      │    ╱│                                                    │
│      │   ╱ │   Multiple edges between 2 and 3                   │
│      │  ╱  │   low[3] = discovery[2] (can reach 2 via other)    │
│      3 ╱───┘                                                    │
│                                                                 │
│  Vertex 2: articulation (low[3] >= discovery[2])                │
│  Edge 2-3: NOT bridge (low[3] = discovery[2], not >)            │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: Maximum Flow

The Flow Network

┌─────────────────────────────────────────────────────────────────┐
│                    FLOW NETWORK CONCEPTS                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Source (S): produces flow                                      │
│  Sink (T): consumes flow                                        │
│  Capacity: maximum flow an edge can carry                       │
│  Flow: actual flow through an edge                              │
│                                                                 │
│         capacity                                                │
│           10                                                    │
│     S ─────────→ A ─────────→ T                                 │
│           flow=7        8                                       │
│                                                                 │
│  Constraints:                                                   │
│  1. Capacity: flow(e) ≤ capacity(e) for all edges               │
│  2. Conservation: flow_in(v) = flow_out(v) for v ≠ S,T          │
│  3. Non-negative: flow(e) ≥ 0                                   │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Ford-Fulkerson Method

The idea: repeatedly find augmenting paths and push flow:

JAVA(70 lines)
Code
Loading syntax highlighter...

Why residual graph works:

┌─────────────────────────────────────────────────────────────────┐
│                 RESIDUAL GRAPH INTUITION                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Original:        After flow=3:      Residual:                  │
│                                                                 │
│     cap=5            flow=3             res=2 (can push 2 more) │
│  S ─────→ T       S ═════→ T         S ─────→ T                 │
│                                       ←─────                    │
│                                        res=3 (can "undo" 3)     │
│                                                                 │
│  Backward edge allows:                                          │
│  - Correcting suboptimal path choices                           │
│  - "Rerouting" flow through better paths                        │
│                                                                 │
│  Example where backward edges are essential:                    │
│                                                                 │
│       ┌─── B ───┐                                               │
│       │   1│1   │                                               │
│    1  │    │    │  1                                            │
│  S ───┴─── A ───┴─── T                                          │
│            1                                                    │
│                                                                 │
│  Path 1: S→B→A→T (flow=1)                                       │
│  Without backward: stuck at max_flow=1                          │
│  With backward: S→A→B→T uses backward A→B, total flow=2         │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Edmonds-Karp Optimization

Using BFS guarantees O(VE²) complexity:

JAVA(87 lines)
Code
Loading syntax highlighter...

Complexity Analysis

Algorithm	Time	Notes
Ford-Fulkerson (DFS)	O(E × max_flow)	Can be slow with large capacities
Edmonds-Karp (BFS)	O(VE²)	Polynomial, practical
Dinic's	O(V²E)	Better for dense graphs
Push-Relabel	O(V²E) or O(V³)	Best for very dense graphs

🔬 Deep Dive: Min-Cut Max-Flow Theorem

The Duality

Theorem: Maximum flow = Minimum cut capacity

┌─────────────────────────────────────────────────────────────────┐
│              MAX-FLOW MIN-CUT DUALITY                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│      ┌─────  5  ─────┐                                          │
│      │               │                                          │
│   S ─┤──── 10 ───────┼── T                                      │
│      │               │                                          │
│      └─────  3  ─────┘                                          │
│                                                                 │
│  Max flow = 18 (5 + 10 + 3)                                     │
│  Min cut = 18 (cut all edges between S and T)                   │
│                                                                 │
│  More complex example:                                          │
│         ┌─── 10 ──→ B ─── 10 ──┐                                │
│         │           │          │                                │
│      S ─┤           5          ├─→ T                            │
│         │           ↓          │                                │
│         └─── 10 ──→ C ─── 10 ──┘                                │
│                                                                 │
│  Bottleneck is edge B→C (capacity 5)                            │
│  Max flow = 15 (10 through B, 5 can cross to C, + 10 through C) │
│  Actually: S→B→T: 10, S→C→T: 10, blocked by B-C                 │
│  Min cut = {B→C, one of S edges} but optimally just 15          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Finding the Min-Cut

After max-flow, perform BFS from source on residual graph:

JAVA(33 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Bipartite Matching

Maximum Bipartite Matching

Find the largest set of edges with no shared vertices:

┌─────────────────────────────────────────────────────────────────┐
│              BIPARTITE MATCHING                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Workers        Jobs           Matching                         │
│                                                                 │
│    A ─────────── 1              A ═══════ 1                     │
│    │  ╲                         │                               │
│    │   ╲                        │                               │
│    B ───╲─────── 2              B ═══════ 2                     │
│    │     ╲   ╱                                                  │
│    │      ╲ ╱                                                   │
│    C ──────╳──── 3              C ═══════ 3                     │
│            ╲                                                    │
│             ╲                                                   │
│    D ────────╲── 4              D (unmatched)                   │
│                                                                 │
│  Maximum matching = 3                                           │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Hungarian Algorithm (Kuhn's Algorithm)

JAVA(58 lines)
Code
Loading syntax highlighter...

Augmenting path intuition:

┌─────────────────────────────────────────────────────────────────┐
│              AUGMENTING PATH IN MATCHING                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Current matching: A-1, B-2                                     │
│  C wants to match but only connects to 1 and 2                  │
│                                                                 │
│    A ═══════ 1       Try C→1: 1 matched to A                    │
│              │       Can A find alternative?                    │
│    B ═══════ 2       A→2: 2 matched to B                        │
│              │       Can B find alternative?                    │
│    C ──────→ 1,2     B→3: 3 unmatched! Success!                 │
│              │                                                  │
│    (unmatched) 3     New matching: A-2, B-3, C-1                │
│                                                                 │
│  Augmenting path: C → 1 → A → 2 → B → 3                         │
│  (alternating unmatched, matched, unmatched, matched, unmatch)  │ 
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Reducing to Max-Flow

Bipartite matching can be solved as max-flow:

JAVA(29 lines)
Code
Loading syntax highlighter...

Hopcroft-Karp Algorithm

For better complexity O(E√V):

JAVA(96 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Wrong Low-Link Update in Tarjan's

JAVA(9 lines)
Code
Loading syntax highlighter...

Why: Back edge target might have updated its low-link through a different path.

Mistake 2: Missing Reverse Edges in Flow

JAVA(14 lines)
Code
Loading syntax highlighter...

Mistake 3: Articulation Point Root Check

JAVA(9 lines)
Code
Loading syntax highlighter...

Why: Non-root vertices use the low-link condition, not children count.

Mistake 4: Visited Array in Bipartite Matching

JAVA(11 lines)
Code
Loading syntax highlighter...

🐛 Debug This: SCC with Incorrect DFS Ordering

This Tarjan's SCC implementation has a subtle bug. Can you find it?

JAVA(54 lines)
Code
Loading syntax highlighter...

🔍 Click to reveal the bug

Bug: In the back edge case, using lowLinks[neighbor] instead of ids[neighbor].

JAVA(9 lines)
Code
Loading syntax highlighter...

Why this matters:

Consider graph: 0 → 1 → 2 → 0

DFS from 0:
  Visit 0: id=0, low=0, stack=[0]
  Visit 1: id=1, low=1, stack=[0,1]
  Visit 2: id=2, low=2, stack=[0,1,2]
    Back edge 2→0:
      With bug: low[2] = min(2, low[0]) = min(2, 0) = 0 ✓
      Actually works here, but...

Consider: 0 → 1 → 2 → 1 (where 2→1 is back edge)

With correct algorithm, when we see back edge 2→1:
  low[2] = min(low[2], id[1]) = min(2, 1) = 1

But if low[1] was updated before we return:
  The buggy version might use an outdated low[1]

The fix ensures we always reference the stable discovery time, not the potentially-changing low-link value.

💻 Exercises

Exercise 1: Find All SCCs ⭐⭐

Implement both Kosaraju's and Tarjan's algorithms and verify they produce the same SCCs.

JAVA(6 lines)
Code
Loading syntax highlighter...

Test case:

Vertices: 8
Edges: 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 6→5, 6→7, 7→6
Expected SCCs: {0,1,2}, {3,4,5}, {6,7}

Exercise 2: Critical Infrastructure ⭐⭐

Given a network of servers and connections, find:

All articulation points (critical servers)
All bridges (critical connections)

JAVA(10 lines)
Code
Loading syntax highlighter...

Exercise 3: Maximum Flow with Multiple Sources ⭐⭐⭐

Modify Edmonds-Karp to handle multiple sources and sinks.

JAVA(6 lines)
Code
Loading syntax highlighter...

Exercise 4: Job Assignment Problem ⭐⭐⭐

Given N workers and M jobs, where worker i can do jobs in skills[i], find maximum number of jobs that can be completed (each worker does at most one job).

JAVA(9 lines)
Code
Loading syntax highlighter...

Exercise 5: Minimum Vertex Cover ⭐⭐⭐⭐

In a bipartite graph, find the minimum set of vertices that covers all edges. Use König's theorem: minimum vertex cover = maximum matching.

JAVA(7 lines)
Code
Loading syntax highlighter...

Hint: After finding max matching:

Start BFS from unmatched left vertices
Alternating between unmatched and matched edges
Minimum vertex cover = (matched left not reached) ∪ (right reached)

🎤 Interview Questions

Q1: "When would you use Tarjan's vs Kosaraju's SCC algorithm?"

Answer: Both have O(V+E) complexity, but differ in practice:

Tarjan's:

Single DFS pass
Lower constant factors
More complex to implement correctly
Outputs SCCs in reverse topological order

Kosaraju's:

Two DFS passes (original + reversed graph)
Easier to understand and implement
Requires building reverse graph (extra O(V+E) space)
More intuitive proof of correctness

Choose Tarjan's when: memory is constrained, or you need the algorithm in competitive programming.

Choose Kosaraju's when: clarity is important, or you're teaching/explaining SCCs.

Q2: "Explain the max-flow min-cut theorem and a practical application."

Answer: The theorem states that in any flow network, the maximum flow from source to sink equals the minimum capacity of any cut separating source from sink.

Intuition:

Maximum flow is limited by some bottleneck
That bottleneck is exactly the minimum cut

Practical application - Image Segmentation:

Problem: Separate foreground from background in image

Model:
- Each pixel is a vertex
- Source connects to "definitely foreground" pixels (∞ capacity)
- Sink connects to "definitely background" pixels (∞ capacity)
- Adjacent pixels connected with capacity = similarity

Min-cut finds optimal boundary between foreground/background
(minimizes cutting through similar pixels)

Q3: "How would you find if a graph has a unique topological ordering?"

Answer: A DAG has a unique topological ordering if and only if there's a Hamiltonian path (path visiting all vertices exactly once).

Algorithm:

JAVA(26 lines)
Code
Loading syntax highlighter...

Q4: "Design a system to match drivers to riders optimally."

Answer: This is a bipartite matching problem with weights (Hungarian algorithm for minimum cost).

JAVA(31 lines)
Code
Loading syntax highlighter...

Considerations:

Real-time updates as drivers/riders appear
Batch matching every few seconds
Consider fairness (don't always assign closest)

Q5: "What's the relationship between articulation points and 2-edge-connected components?"

Answer:

Articulation points split the graph into biconnected components (2-vertex-connected). Bridges split the graph into 2-edge-connected components.

2-vertex-connected: Remains connected after removing any single vertex
2-edge-connected: Remains connected after removing any single edge

Relationship:
- Every bridge's endpoints are articulation points (unless degree 1)
- Articulation point doesn't always imply bridge exists

Example:
    A --- B
    |  X  |     (X marks diagonal edges)
    C --- D

No bridges (every edge is in a cycle)
No articulation points (2-vertex-connected)

vs:

    A --- B --- E
    |     |
    C --- D

B is articulation point
B-E is a bridge

📋 Quick Reference

Algorithm Complexity

Algorithm	Time	Space	Use Case
Kosaraju's SCC	O(V+E)	O(V+E)	Find strongly connected components
Tarjan's SCC	O(V+E)	O(V)	Find SCCs, single pass
Articulation Points	O(V+E)	O(V)	Find critical vertices
Bridges	O(V+E)	O(V)	Find critical edges
Ford-Fulkerson	O(E × max_flow)	O(V²)	Max flow (integer capacities)
Edmonds-Karp	O(VE²)	O(V²)	Max flow (polynomial)
Hungarian	O(V³)	O(V²)	Min cost bipartite matching
Hopcroft-Karp	O(E√V)	O(V)	Max bipartite matching

Key Formulas

SCC Root Condition:     ids[v] == lowLinks[v]
Articulation (root):    children > 1
Articulation (non-root): lowLinks[child] >= ids[v]
Bridge Condition:       lowLinks[v] > ids[parent]
Max-Flow = Min-Cut:     Always true (duality theorem)
König's Theorem:        Min Vertex Cover = Max Matching (bipartite)

Code Templates

JAVA(14 lines)
Code
Loading syntax highlighter...

🔗 What's Next?

In Part 15: Graph Algorithms in Practice, we'll explore:

Social network analysis
Recommendation systems
PageRank algorithm
Community detection
Real-world case studies

📅 Review Schedule

Day	Focus	Time
0	Full read + exercises	90 min
1	Quick Reference + SCCs	10 min
3	Implement Tarjan's from memory	20 min
7	Max-flow problem	15 min
14	Debug exercise + bipartite matching	15 min
30	All interview questions	10 min

Next: Part 15: Graph Algorithms in Practice →

Series: Algorithms Compendium Index