[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":87,"_73":88,"_35":89},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",41,"title","Advanced Graph Algorithms","slug","algorithms-part-14-advanced-graph-algorithms","excerpt","Find Strongly Connected Components with Tarjan's/Kosaraju's, identify bridges, solve maximum flow with Ford-Fulkerson, and implement bipartite matching.","# Part 14: Advanced Graph Algorithms - SCCs, Flows, and Matching\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 35 minutes |\n| Prerequisites | Part 11 (Graph Traversal), Part 12 (Shortest Path) |\n| Key Concepts | Strongly Connected Components, Articulation Points, Max Flow, Bipartite Matching |\n| Difficulty | ⭐⭐⭐⭐ (Advanced) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ ADVANCED GRAPH ALGORITHMS LANDSCAPE │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ CONNECTIVITY FLOW NETWORKS │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Strongly │ │ Maximum Flow │ │\n│ │ Connected │ │ ─────────────── │ │\n│ │ Components │ │ Ford-Fulkerson │ │\n│ │ ─────────────── │ │ Edmonds-Karp │ │\n│ │ Tarjan's O(V+E) │ │ Push-Relabel │ │\n│ │ Kosaraju's │ └─────────────────┘ │\n│ └─────────────────┘ │ │\n│ │ │ │\n│ ▼ ▼ │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Critical Points │ │ Min Cut │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ Articulation │ │ Max-Flow = │ │\n│ │ Points │ │ Min-Cut │ │\n│ │ Bridges │ │ (Duality) │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │ │\n│ ▼ │\n│ ┌─────────────────┐ │\n│ │ Bipartite │ │\n│ │ Matching │ │\n│ │ ─────────────── │ │\n│ │ Hungarian Alg │ │\n│ │ Hopcroft-Karp │ │\n│ └─────────────────┘ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Find SCCs**: Implement Tarjan's and Kosaraju's algorithms\n2. **Identify critical points**: Find articulation points and bridges\n3. **Solve flow problems**: Apply Ford-Fulkerson and Edmonds-Karp\n4. **Match bipartite graphs**: Use Hungarian algorithm for optimal assignment\n5. **Apply min-cut**: Understand max-flow min-cut duality\n\n---\n\n## 🔥 Production Story: The Microservice Dependency Nightmare\n\nA fintech company's platform grew to 200+ microservices. One Monday morning, a seemingly minor deployment caused a cascade failure affecting 40% of the system.\n\n### The Incident\n\n```\n08:15 - Payment service deployed new version\n08:17 - Order service health checks failing\n08:19 - Inventory service unresponsive\n08:22 - Customer dashboard showing errors\n08:25 - Trading halted, revenue loss: $50K/minute\n```\n\nThe team had no visibility into service dependencies. They couldn't answer:\n- Which services form tightly coupled groups?\n- Which services, if they fail, would partition the system?\n- What's the maximum throughput between any two services?\n\n### The Investigation\n\nThe architect analyzed the call graph:\n\n```java\n// ❌ No understanding of dependency structure\npublic class ServiceRegistry {\n private Map> dependencies = new HashMap<>();\n\n public void registerDependency(String from, String to) {\n dependencies.computeIfAbsent(from, k -> new ArrayList<>()).add(to);\n }\n\n // \"Let's just restart everything and hope for the best\"\n public void handleFailure(String failedService) {\n System.out.println(\"Service failed: \" + failedService);\n // No intelligent recovery strategy\n }\n}\n```\n\n### The Solution\n\nThey applied advanced graph algorithms:\n\n```java\n// ✅ Understanding system topology with graph algorithms\npublic class ServiceTopologyAnalyzer {\n private final Map> graph;\n private final Map> reverseGraph;\n\n // 1. Find Strongly Connected Components (tightly coupled services)\n public List> findServiceClusters() {\n return new KosarajuSCC(graph, reverseGraph).findSCCs();\n }\n\n // 2. Find articulation points (single points of failure)\n public Set findCriticalServices() {\n return new ArticulationPointFinder(graph).find();\n }\n\n // 3. Find bridges (critical connections)\n public List findCriticalConnections() {\n return new BridgeFinder(graph).find();\n }\n\n // 4. Calculate max throughput between services\n public int maxThroughput(String source, String sink) {\n return new EdmondsKarp(capacityGraph).maxFlow(source, sink);\n }\n\n // Intelligent failure handling\n public RecoveryPlan handleFailure(String failedService) {\n Set affected = findAffectedServices(failedService);\n List> clusters = findServiceClusters();\n\n // Find which cluster is affected\n Set affectedCluster = clusters.stream()\n .filter(c -> c.contains(failedService))\n .findFirst()\n .orElse(Collections.emptySet());\n\n return new RecoveryPlan(affectedCluster,\n isCriticalService(failedService));\n }\n}\n```\n\n### The Impact\n\n| Metric | Before | After |\n|--------|--------|-------|\n| Mean Time to Recovery | 45 minutes | 8 minutes |\n| Cascade failures/month | 12 | 1 |\n| Critical services identified | 0 | 23 |\n| Deployment confidence | Low | High |\n\n**The insight**: Understanding graph structure transforms reactive firefighting into proactive architecture.\n\n---\n\n## 🧠 Mental Model: The City Infrastructure\n\nThink of advanced graph algorithms as city planning tools:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ CITY INFRASTRUCTURE │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ STRONGLY CONNECTED ARTICULATION POINTS │\n│ COMPONENTS (Single Points of Failure) │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Downtown │ │ │ │\n│ │ ┌───┐ ┌───┐ │ │ A ─── B │ │\n│ │ │ A │──│ B │ │ │ │ │ │\n│ │ └─┬─┘ └─┬─┘ │ │ ▼ │ │\n│ │ │ ╲╱ │ │ │ [C] ◄─────── │ C is │\n│ │ │ ╱╲ │ │ │ │ critical │\n│ │ ┌─┴─┐ ┌─┴─┐ │ │ ▼ │ │\n│ │ │ C │──│ D │ │ │ D ─── E │ │\n│ │ └───┘ └───┘ │ │ │ │\n│ │ All reachable │ └─────────────────┘ │\n│ │ from each other │ │\n│ └─────────────────┘ │\n│ │\n│ MAX FLOW BIPARTITE MATCHING │\n│ (Traffic Capacity) (Job Assignment) │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ 8 5 │ │ Workers Jobs │ │\n│ │ A ───→ B ───→ │ │ A ──── 1 │ │\n│ │ │ │ T │ │ B ──┬─ 2 │ │\n│ │ │3 │2 │ │ C ──┘─ 3 │ │\n│ │ ▼ ▼ │ │ │ │\n│ │ S ───→ C ───→ │ │ Maximum │ │\n│ │ 6 4 │ │ matching = 3 │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Key analogies**:\n- **SCC** = Neighborhoods where you can walk from any point to any other\n- **Articulation Point** = The only bridge connecting two parts of city\n- **Max Flow** = Maximum traffic the road network can handle\n- **Bipartite Matching** = Assigning taxi drivers to passengers optimally\n\n---\n\n## 🔬 Deep Dive: Strongly Connected Components\n\n### Understanding SCCs\n\nA **Strongly Connected Component** is a maximal set of vertices where every vertex is reachable from every other vertex.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ SCC VISUALIZATION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Original Graph: SCCs Identified: │\n│ │\n│ 1 ──→ 2 ┌─────────┐ │\n│ ↑ ↓ │ SCC 1 │ │\n│ └──── 3 ──→ 4 │ {1,2,3} │──→ {4} ──→ {5,6} │\n│ ↓ └─────────┘ SCC2 SCC3 │\n│ 5 ←── 6 │\n│ └────→ │\n│ │\n│ Within SCC: bidirectional reachability │\n│ Between SCCs: DAG (no cycles possible) │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Kosaraju's Algorithm\n\nKosaraju's uses two DFS passes - one on original graph, one on reversed:\n\n```java\npublic class KosarajuSCC {\n private final Map> graph;\n private final Map> reverseGraph;\n private final int vertices;\n\n public KosarajuSCC(int vertices) {\n this.vertices = vertices;\n this.graph = new HashMap<>();\n this.reverseGraph = new HashMap<>();\n for (int i = 0; i < vertices; i++) {\n graph.put(i, new ArrayList<>());\n reverseGraph.put(i, new ArrayList<>());\n }\n }\n\n public void addEdge(int from, int to) {\n graph.get(from).add(to);\n reverseGraph.get(to).add(from); // Reverse edge\n }\n\n public List> findSCCs() {\n // Step 1: Get vertices in order of finish time\n Deque finishOrder = new ArrayDeque<>();\n boolean[] visited = new boolean[vertices];\n\n for (int v = 0; v < vertices; v++) {\n if (!visited[v]) {\n fillOrder(v, visited, finishOrder);\n }\n }\n\n // Step 2: Process vertices in reverse finish order on reversed graph\n Arrays.fill(visited, false);\n List> sccs = new ArrayList<>();\n\n while (!finishOrder.isEmpty()) {\n int v = finishOrder.pop();\n if (!visited[v]) {\n List component = new ArrayList<>();\n dfsReverse(v, visited, component);\n sccs.add(component);\n }\n }\n\n return sccs;\n }\n\n private void fillOrder(int v, boolean[] visited, Deque stack) {\n visited[v] = true;\n for (int neighbor : graph.get(v)) {\n if (!visited[neighbor]) {\n fillOrder(neighbor, visited, stack);\n }\n }\n stack.push(v); // Push after processing all descendants\n }\n\n private void dfsReverse(int v, boolean[] visited, List component) {\n visited[v] = true;\n component.add(v);\n for (int neighbor : reverseGraph.get(v)) {\n if (!visited[neighbor]) {\n dfsReverse(neighbor, visited, component);\n }\n }\n }\n}\n```\n\n**Why it works**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ KOSARAJU'S INTUITION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Pass 1: Record finish times │\n│ ───────────────────────────── │\n│ Vertices that finish later can reach more vertices │\n│ (they're \"upstream\" in the SCC DAG) │\n│ │\n│ SCC_A ──→ SCC_B ──→ SCC_C │\n│ ▲ │\n│ │ │\n│ Finishes last (can reach B and C) │\n│ │\n│ Pass 2: DFS on reversed graph │\n│ ───────────────────────────── │\n│ Starting from highest finish time: │\n│ - Can only reach vertices in SAME SCC │\n│ - Reverse edges prevent crossing to other SCCs │\n│ │\n│ SCC_A ←── SCC_B ←── SCC_C (reversed) │\n│ │ │\n│ └── Start here, stays in SCC_A │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Tarjan's Algorithm\n\nTarjan's is more elegant - single DFS pass using low-link values:\n\n```java\npublic class TarjanSCC {\n private final Map> graph;\n private final int vertices;\n\n private int[] ids; // Discovery time of each vertex\n private int[] lowLinks; // Lowest reachable vertex\n private boolean[] onStack; // Currently on the recursion stack\n private Deque stack;\n private int id; // Current discovery time\n private List> sccs;\n\n public TarjanSCC(int vertices) {\n this.vertices = vertices;\n this.graph = new HashMap<>();\n for (int i = 0; i < vertices; i++) {\n graph.put(i, new ArrayList<>());\n }\n }\n\n public void addEdge(int from, int to) {\n graph.get(from).add(to);\n }\n\n public List> findSCCs() {\n ids = new int[vertices];\n lowLinks = new int[vertices];\n onStack = new boolean[vertices];\n stack = new ArrayDeque<>();\n sccs = new ArrayList<>();\n id = 0;\n\n Arrays.fill(ids, -1); // -1 means unvisited\n\n for (int v = 0; v < vertices; v++) {\n if (ids[v] == -1) {\n dfs(v);\n }\n }\n\n return sccs;\n }\n\n private void dfs(int v) {\n // Initialize vertex\n ids[v] = lowLinks[v] = id++;\n stack.push(v);\n onStack[v] = true;\n\n // Explore neighbors\n for (int neighbor : graph.get(v)) {\n if (ids[neighbor] == -1) {\n // Unvisited - recurse\n dfs(neighbor);\n // Update low-link on return\n lowLinks[v] = Math.min(lowLinks[v], lowLinks[neighbor]);\n } else if (onStack[neighbor]) {\n // Back edge to vertex on stack\n lowLinks[v] = Math.min(lowLinks[v], ids[neighbor]);\n }\n // Cross edges to completed SCCs are ignored\n }\n\n // If v is root of an SCC\n if (ids[v] == lowLinks[v]) {\n List component = new ArrayList<>();\n while (true) {\n int w = stack.pop();\n onStack[w] = false;\n component.add(w);\n if (w == v) break;\n }\n sccs.add(component);\n }\n }\n}\n```\n\n**Low-link visualization**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ TARJAN'S LOW-LINK │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Discovery order: 1 → 2 → 3 → 4 │\n│ │\n│ 1 ────→ 2 ids: 1 2 3 4 │\n│ ↑ ↓ lowLinks: 1 1 1 4 │\n│ └────── 3 ────→ 4 │\n│ │\n│ Back edge 3→1 updates lowLinks: │\n│ - lowLink[3] = min(3, id[1]) = 1 │\n│ - lowLink[2] = min(2, lowLink[3]) = 1 │\n│ - lowLink[1] = min(1, lowLink[2]) = 1 │\n│ │\n│ SCC roots: vertices where id[v] == lowLink[v] │\n│ - Vertex 1: id=1, lowLink=1 → ROOT of SCC {1,2,3} │\n│ - Vertex 4: id=4, lowLink=4 → ROOT of SCC {4} │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Comparison\n\n| Aspect | Kosaraju's | Tarjan's |\n|--------|------------|----------|\n| DFS passes | 2 | 1 |\n| Extra space | O(V) for reverse graph | O(V) for stack |\n| Simplicity | Easier to understand | More elegant |\n| Constants | Slightly higher | Lower |\n| Output order | Reverse topological | Reverse topological |\n\n---\n\n## 🔬 Deep Dive: Articulation Points and Bridges\n\n### Articulation Points\n\nAn **articulation point** (cut vertex) is a vertex whose removal disconnects the graph.\n\n```java\npublic class ArticulationPoints {\n private final Map> graph;\n private final int vertices;\n\n private int[] discovery;\n private int[] low;\n private int[] parent;\n private boolean[] isArticulation;\n private int time;\n\n public ArticulationPoints(int vertices) {\n this.vertices = vertices;\n this.graph = new HashMap<>();\n for (int i = 0; i < vertices; i++) {\n graph.put(i, new ArrayList<>());\n }\n }\n\n public void addEdge(int u, int v) {\n graph.get(u).add(v);\n graph.get(v).add(u); // Undirected graph\n }\n\n public List find() {\n discovery = new int[vertices];\n low = new int[vertices];\n parent = new int[vertices];\n isArticulation = new boolean[vertices];\n time = 0;\n\n Arrays.fill(discovery, -1);\n Arrays.fill(parent, -1);\n\n // Handle disconnected graphs\n for (int v = 0; v < vertices; v++) {\n if (discovery[v] == -1) {\n dfs(v);\n }\n }\n\n List result = new ArrayList<>();\n for (int v = 0; v < vertices; v++) {\n if (isArticulation[v]) {\n result.add(v);\n }\n }\n return result;\n }\n\n private void dfs(int u) {\n int children = 0;\n discovery[u] = low[u] = time++;\n\n for (int v : graph.get(u)) {\n if (discovery[v] == -1) {\n // Tree edge\n children++;\n parent[v] = u;\n dfs(v);\n\n // Update low value\n low[u] = Math.min(low[u], low[v]);\n\n // Articulation point conditions:\n\n // 1. Root with 2+ children\n if (parent[u] == -1 && children > 1) {\n isArticulation[u] = true;\n }\n\n // 2. Non-root where child can't reach ancestor\n if (parent[u] != -1 && low[v] >= discovery[u]) {\n isArticulation[u] = true;\n }\n } else if (v != parent[u]) {\n // Back edge (not to parent)\n low[u] = Math.min(low[u], discovery[v]);\n }\n }\n }\n}\n```\n\n**Why the conditions work**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ ARTICULATION POINT CONDITIONS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Condition 1: Root with 2+ children │\n│ ────────────────────────────────── │\n│ ┌───┐ │\n│ │ R │ ← Root │\n│ ╱ ╲ │\n│ ┌───┐ ┌───┐ │\n│ │ A │ │ B │ Two subtrees │\n│ └───┘ └───┘ │\n│ │\n│ If R is removed, A and B are disconnected │\n│ (children in DFS tree have no other connection) │\n│ │\n│ Condition 2: low[v] >= discovery[u] │\n│ ─────────────────────────────────── │\n│ 1 │\n│ ╱│ │\n│ 2 │ discovery[1]=0, low[1]=0 │\n│ ╱│ │ discovery[2]=1, low[2]=0 (back edge to 1) │\n│ 3 │ │ discovery[3]=2, low[3]=2 (no back edge!) │\n│ │ │ │\n│ └─┘ low[3] >= discovery[2] → 2 is articulation │\n│ (3 can't reach above 2 without going through 2) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Bridges\n\nA **bridge** is an edge whose removal disconnects the graph:\n\n```java\npublic class Bridges {\n private final Map> graph;\n private final int vertices;\n\n private int[] discovery;\n private int[] low;\n private int[] parent;\n private List bridges;\n private int time;\n\n public Bridges(int vertices) {\n this.vertices = vertices;\n this.graph = new HashMap<>();\n for (int i = 0; i < vertices; i++) {\n graph.put(i, new ArrayList<>());\n }\n }\n\n public void addEdge(int u, int v) {\n graph.get(u).add(v);\n graph.get(v).add(u);\n }\n\n public List find() {\n discovery = new int[vertices];\n low = new int[vertices];\n parent = new int[vertices];\n bridges = new ArrayList<>();\n time = 0;\n\n Arrays.fill(discovery, -1);\n Arrays.fill(parent, -1);\n\n for (int v = 0; v < vertices; v++) {\n if (discovery[v] == -1) {\n dfs(v);\n }\n }\n\n return bridges;\n }\n\n private void dfs(int u) {\n discovery[u] = low[u] = time++;\n\n for (int v : graph.get(u)) {\n if (discovery[v] == -1) {\n parent[v] = u;\n dfs(v);\n\n low[u] = Math.min(low[u], low[v]);\n\n // Bridge condition: low[v] > discovery[u]\n // (strictly greater, not >=)\n if (low[v] > discovery[u]) {\n bridges.add(new int[]{u, v});\n }\n } else if (v != parent[u]) {\n low[u] = Math.min(low[u], discovery[v]);\n }\n }\n }\n}\n```\n\n**Bridge vs Articulation Point**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BRIDGE vs ARTICULATION POINT │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Articulation: low[v] >= discovery[u] │\n│ Bridge: low[v] > discovery[u] │\n│ │\n│ Example where u is articulation but (u,v) is NOT bridge: │\n│ │\n│ 1 ─── 2 │\n│ │ ╱│ │\n│ │ ╱ │ Multiple edges between 2 and 3 │\n│ │ ╱ │ low[3] = discovery[2] (can reach 2 via other) │\n│ 3 ╱───┘ │\n│ │\n│ Vertex 2: articulation (low[3] >= discovery[2]) │\n│ Edge 2-3: NOT bridge (low[3] = discovery[2], not >) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Maximum Flow\n\n### The Flow Network\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ FLOW NETWORK CONCEPTS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Source (S): produces flow │\n│ Sink (T): consumes flow │\n│ Capacity: maximum flow an edge can carry │\n│ Flow: actual flow through an edge │\n│ │\n│ capacity │\n│ 10 │\n│ S ─────────→ A ─────────→ T │\n│ flow=7 8 │\n│ │\n│ Constraints: │\n│ 1. Capacity: flow(e) ≤ capacity(e) for all edges │\n│ 2. Conservation: flow_in(v) = flow_out(v) for v ≠ S,T │\n│ 3. Non-negative: flow(e) ≥ 0 │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Ford-Fulkerson Method\n\nThe idea: repeatedly find augmenting paths and push flow:\n\n```java\npublic class FordFulkerson {\n private final int vertices;\n private int[][] capacity; // Original capacities\n private int[][] residual; // Residual capacities\n\n public FordFulkerson(int vertices) {\n this.vertices = vertices;\n this.capacity = new int[vertices][vertices];\n this.residual = new int[vertices][vertices];\n }\n\n public void addEdge(int from, int to, int cap) {\n capacity[from][to] = cap;\n residual[from][to] = cap;\n }\n\n public int maxFlow(int source, int sink) {\n int maxFlow = 0;\n int[] parent = new int[vertices];\n\n // While there's an augmenting path\n while (bfs(source, sink, parent)) {\n // Find minimum residual capacity along path\n int pathFlow = Integer.MAX_VALUE;\n for (int v = sink; v != source; v = parent[v]) {\n int u = parent[v];\n pathFlow = Math.min(pathFlow, residual[u][v]);\n }\n\n // Update residual capacities\n for (int v = sink; v != source; v = parent[v]) {\n int u = parent[v];\n residual[u][v] -= pathFlow; // Reduce forward\n residual[v][u] += pathFlow; // Increase backward\n }\n\n maxFlow += pathFlow;\n }\n\n return maxFlow;\n }\n\n // BFS to find augmenting path (Edmonds-Karp)\n private boolean bfs(int source, int sink, int[] parent) {\n boolean[] visited = new boolean[vertices];\n Queue queue = new LinkedList<>();\n\n queue.offer(source);\n visited[source] = true;\n parent[source] = -1;\n\n while (!queue.isEmpty()) {\n int u = queue.poll();\n\n for (int v = 0; v < vertices; v++) {\n if (!visited[v] && residual[u][v] > 0) {\n queue.offer(v);\n visited[v] = true;\n parent[v] = u;\n\n if (v == sink) {\n return true;\n }\n }\n }\n }\n\n return false;\n }\n}\n```\n\n**Why residual graph works**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ RESIDUAL GRAPH INTUITION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Original: After flow=3: Residual: │\n│ │\n│ cap=5 flow=3 res=2 (can push 2 more) │\n│ S ─────→ T S ═════→ T S ─────→ T │\n│ ←───── │\n│ res=3 (can \"undo\" 3) │\n│ │\n│ Backward edge allows: │\n│ - Correcting suboptimal path choices │\n│ - \"Rerouting\" flow through better paths │\n│ │\n│ Example where backward edges are essential: │\n│ │\n│ ┌─── B ───┐ │\n│ │ 1│1 │ │\n│ 1 │ │ │ 1 │\n│ S ───┴─── A ───┴─── T │\n│ 1 │\n│ │\n│ Path 1: S→B→A→T (flow=1) │\n│ Without backward: stuck at max_flow=1 │\n│ With backward: S→A→B→T uses backward A→B, total flow=2 │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Edmonds-Karp Optimization\n\nUsing BFS guarantees O(VE²) complexity:\n\n```java\npublic class EdmondsKarp {\n private final int vertices;\n private final List> graph;\n\n static class Edge {\n int to, capacity, flow;\n Edge reverse; // Pointer to reverse edge\n\n Edge(int to, int capacity) {\n this.to = to;\n this.capacity = capacity;\n this.flow = 0;\n }\n\n int residual() {\n return capacity - flow;\n }\n\n void augment(int amount) {\n flow += amount;\n reverse.flow -= amount;\n }\n }\n\n public EdmondsKarp(int vertices) {\n this.vertices = vertices;\n this.graph = new ArrayList<>();\n for (int i = 0; i < vertices; i++) {\n graph.add(new ArrayList<>());\n }\n }\n\n public void addEdge(int from, int to, int capacity) {\n Edge forward = new Edge(to, capacity);\n Edge backward = new Edge(from, 0); // Reverse with 0 capacity\n forward.reverse = backward;\n backward.reverse = forward;\n graph.get(from).add(forward);\n graph.get(to).add(backward);\n }\n\n public int maxFlow(int source, int sink) {\n int maxFlow = 0;\n\n while (true) {\n // BFS to find shortest augmenting path\n Edge[] parent = new Edge[vertices];\n boolean[] visited = new boolean[vertices];\n Queue queue = new LinkedList<>();\n\n queue.offer(source);\n visited[source] = true;\n\n while (!queue.isEmpty() && !visited[sink]) {\n int u = queue.poll();\n for (Edge e : graph.get(u)) {\n if (!visited[e.to] && e.residual() > 0) {\n visited[e.to] = true;\n parent[e.to] = e;\n queue.offer(e.to);\n }\n }\n }\n\n if (!visited[sink]) break; // No augmenting path\n\n // Find bottleneck\n int pathFlow = Integer.MAX_VALUE;\n for (int v = sink; v != source; ) {\n Edge e = parent[v];\n pathFlow = Math.min(pathFlow, e.residual());\n v = e.reverse.to;\n }\n\n // Augment flow\n for (int v = sink; v != source; ) {\n Edge e = parent[v];\n e.augment(pathFlow);\n v = e.reverse.to;\n }\n\n maxFlow += pathFlow;\n }\n\n return maxFlow;\n }\n}\n```\n\n### Complexity Analysis\n\n| Algorithm | Time | Notes |\n|-----------|------|-------|\n| Ford-Fulkerson (DFS) | O(E × max_flow) | Can be slow with large capacities |\n| Edmonds-Karp (BFS) | O(VE²) | Polynomial, practical |\n| Dinic's | O(V²E) | Better for dense graphs |\n| Push-Relabel | O(V²E) or O(V³) | Best for very dense graphs |\n\n---\n\n## 🔬 Deep Dive: Min-Cut Max-Flow Theorem\n\n### The Duality\n\n**Theorem**: Maximum flow = Minimum cut capacity\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ MAX-FLOW MIN-CUT DUALITY │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ ┌───── 5 ─────┐ │\n│ │ │ │\n│ S ─┤──── 10 ───────┼── T │\n│ │ │ │\n│ └───── 3 ─────┘ │\n│ │\n│ Max flow = 18 (5 + 10 + 3) │\n│ Min cut = 18 (cut all edges between S and T) │\n│ │\n│ More complex example: │\n│ ┌─── 10 ──→ B ─── 10 ──┐ │\n│ │ │ │ │\n│ S ─┤ 5 ├─→ T │\n│ │ ↓ │ │\n│ └─── 10 ──→ C ─── 10 ──┘ │\n│ │\n│ Bottleneck is edge B→C (capacity 5) │\n│ Max flow = 15 (10 through B, 5 can cross to C, + 10 through C) │\n│ Actually: S→B→T: 10, S→C→T: 10, blocked by B-C │\n│ Min cut = {B→C, one of S edges} but optimally just 15 │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Finding the Min-Cut\n\nAfter max-flow, perform BFS from source on residual graph:\n\n```java\npublic List findMinCut(int source) {\n // After running maxFlow()\n\n // BFS from source on residual graph\n boolean[] reachable = new boolean[vertices];\n Queue queue = new LinkedList<>();\n queue.offer(source);\n reachable[source] = true;\n\n while (!queue.isEmpty()) {\n int u = queue.poll();\n for (Edge e : graph.get(u)) {\n if (!reachable[e.to] && e.residual() > 0) {\n reachable[e.to] = true;\n queue.offer(e.to);\n }\n }\n }\n\n // Min-cut edges: from reachable to non-reachable\n List minCut = new ArrayList<>();\n for (int u = 0; u < vertices; u++) {\n if (reachable[u]) {\n for (Edge e : graph.get(u)) {\n if (!reachable[e.to] && e.capacity > 0) {\n minCut.add(new int[]{u, e.to});\n }\n }\n }\n }\n\n return minCut;\n}\n```\n\n---\n\n## 🔬 Deep Dive: Bipartite Matching\n\n### Maximum Bipartite Matching\n\nFind the largest set of edges with no shared vertices:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BIPARTITE MATCHING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Workers Jobs Matching │\n│ │\n│ A ─────────── 1 A ═══════ 1 │\n│ │ ╲ │ │\n│ │ ╲ │ │\n│ B ───╲─────── 2 B ═══════ 2 │\n│ │ ╲ ╱ │\n│ │ ╲ ╱ │\n│ C ──────╳──── 3 C ═══════ 3 │\n│ ╲ │\n│ ╲ │\n│ D ────────╲── 4 D (unmatched) │\n│ │\n│ Maximum matching = 3 │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Hungarian Algorithm (Kuhn's Algorithm)\n\n```java\npublic class BipartiteMatching {\n private final int leftSize, rightSize;\n private final List> adj; // Left to right edges\n private int[] matchLeft; // matchLeft[l] = matched right vertex\n private int[] matchRight; // matchRight[r] = matched left vertex\n private boolean[] visited;\n\n public BipartiteMatching(int leftSize, int rightSize) {\n this.leftSize = leftSize;\n this.rightSize = rightSize;\n this.adj = new ArrayList<>();\n for (int i = 0; i < leftSize; i++) {\n adj.add(new ArrayList<>());\n }\n }\n\n public void addEdge(int left, int right) {\n adj.get(left).add(right);\n }\n\n public int maxMatching() {\n matchLeft = new int[leftSize];\n matchRight = new int[rightSize];\n Arrays.fill(matchLeft, -1);\n Arrays.fill(matchRight, -1);\n\n int matching = 0;\n\n for (int u = 0; u < leftSize; u++) {\n visited = new boolean[rightSize];\n if (dfs(u)) {\n matching++;\n }\n }\n\n return matching;\n }\n\n // Try to find augmenting path starting from left vertex u\n private boolean dfs(int u) {\n for (int v : adj.get(u)) {\n if (visited[v]) continue;\n visited[v] = true;\n\n // If v is unmatched OR we can reroute v's current match\n if (matchRight[v] == -1 || dfs(matchRight[v])) {\n matchLeft[u] = v;\n matchRight[v] = u;\n return true;\n }\n }\n return false;\n }\n\n public int[] getMatching() {\n return matchLeft;\n }\n}\n```\n\n**Augmenting path intuition**:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ AUGMENTING PATH IN MATCHING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Current matching: A-1, B-2 │\n│ C wants to match but only connects to 1 and 2 │\n│ │\n│ A ═══════ 1 Try C→1: 1 matched to A │\n│ │ Can A find alternative? │\n│ B ═══════ 2 A→2: 2 matched to B │\n│ │ Can B find alternative? │\n│ C ──────→ 1,2 B→3: 3 unmatched! Success! │\n│ │ │\n│ (unmatched) 3 New matching: A-2, B-3, C-1 │\n│ │\n│ Augmenting path: C → 1 → A → 2 → B → 3 │\n│ (alternating unmatched, matched, unmatched, matched, unmatch) │ \n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Reducing to Max-Flow\n\nBipartite matching can be solved as max-flow:\n\n```java\npublic int maxMatchingViaFlow(int leftSize, int rightSize,\n List edges) {\n // Create flow network:\n // - Super source (0) connects to all left vertices\n // - All right vertices connect to super sink (leftSize + rightSize + 1)\n // - All capacities = 1\n\n int source = 0;\n int sink = leftSize + rightSize + 1;\n EdmondsKarp flow = new EdmondsKarp(sink + 1);\n\n // Source to left vertices\n for (int l = 0; l < leftSize; l++) {\n flow.addEdge(source, l + 1, 1);\n }\n\n // Right vertices to sink\n for (int r = 0; r < rightSize; r++) {\n flow.addEdge(leftSize + r + 1, sink, 1);\n }\n\n // Left to right edges\n for (int[] edge : edges) {\n int l = edge[0], r = edge[1];\n flow.addEdge(l + 1, leftSize + r + 1, 1);\n }\n\n return flow.maxFlow(source, sink);\n}\n```\n\n### Hopcroft-Karp Algorithm\n\nFor better complexity O(E√V):\n\n```java\npublic class HopcroftKarp {\n private final int leftSize, rightSize;\n private final List> adj;\n private int[] matchLeft, matchRight;\n private int[] dist;\n\n private static final int NIL = -1;\n private static final int INF = Integer.MAX_VALUE;\n\n public HopcroftKarp(int leftSize, int rightSize) {\n this.leftSize = leftSize;\n this.rightSize = rightSize;\n this.adj = new ArrayList<>();\n for (int i = 0; i < leftSize; i++) {\n adj.add(new ArrayList<>());\n }\n }\n\n public void addEdge(int left, int right) {\n adj.get(left).add(right);\n }\n\n public int maxMatching() {\n matchLeft = new int[leftSize];\n matchRight = new int[rightSize];\n dist = new int[leftSize + 1]; // dist[leftSize] = dist[NIL]\n\n Arrays.fill(matchLeft, NIL);\n Arrays.fill(matchRight, NIL);\n\n int matching = 0;\n\n // Find augmenting paths in phases\n while (bfs()) {\n for (int u = 0; u < leftSize; u++) {\n if (matchLeft[u] == NIL && dfs(u)) {\n matching++;\n }\n }\n }\n\n return matching;\n }\n\n // BFS to build level graph of shortest augmenting paths\n private boolean bfs() {\n Queue queue = new LinkedList<>();\n\n for (int u = 0; u < leftSize; u++) {\n if (matchLeft[u] == NIL) {\n dist[u] = 0;\n queue.offer(u);\n } else {\n dist[u] = INF;\n }\n }\n dist[leftSize] = INF; // NIL distance\n\n while (!queue.isEmpty()) {\n int u = queue.poll();\n if (dist[u] < dist[leftSize]) {\n for (int v : adj.get(u)) {\n int pairV = matchRight[v];\n int pairIdx = (pairV == NIL) ? leftSize : pairV;\n if (dist[pairIdx] == INF) {\n dist[pairIdx] = dist[u] + 1;\n if (pairV != NIL) {\n queue.offer(pairV);\n }\n }\n }\n }\n }\n\n return dist[leftSize] != INF;\n }\n\n // DFS to find augmenting paths along level graph\n private boolean dfs(int u) {\n if (u == leftSize) return true; // Reached NIL\n\n for (int v : adj.get(u)) {\n int pairV = matchRight[v];\n int pairIdx = (pairV == NIL) ? leftSize : pairV;\n\n if (dist[pairIdx] == dist[u] + 1 && dfs(pairIdx)) {\n matchRight[v] = u;\n matchLeft[u] = v;\n return true;\n }\n }\n\n dist[u] = INF; // Remove from level graph\n return false;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Wrong Low-Link Update in Tarjan's\n\n```java\n// ❌ WRONG: Update low-link with low-link of back edge target\nif (onStack[neighbor]) {\n lowLinks[v] = Math.min(lowLinks[v], lowLinks[neighbor]); // Bug!\n}\n\n// ✅ CORRECT: Update with discovery time (id) of back edge target\nif (onStack[neighbor]) {\n lowLinks[v] = Math.min(lowLinks[v], ids[neighbor]);\n}\n```\n\n**Why**: Back edge target might have updated its low-link through a different path.\n\n---\n\n### Mistake 2: Missing Reverse Edges in Flow\n\n```java\n// ❌ WRONG: Only adding forward edge\npublic void addEdge(int from, int to, int capacity) {\n graph[from].add(new Edge(to, capacity));\n}\n\n// ✅ CORRECT: Add both forward and reverse edges\npublic void addEdge(int from, int to, int capacity) {\n Edge forward = new Edge(to, capacity);\n Edge backward = new Edge(from, 0);\n forward.reverse = backward;\n backward.reverse = forward;\n graph[from].add(forward);\n graph[to].add(backward);\n}\n```\n\n---\n\n### Mistake 3: Articulation Point Root Check\n\n```java\n// ❌ WRONG: Checking children count after all DFS\nif (children > 1) {\n isArticulation[u] = true;\n}\n\n// ✅ CORRECT: Check only if u is root (parent[u] == -1)\nif (parent[u] == -1 && children > 1) {\n isArticulation[u] = true;\n}\n```\n\n**Why**: Non-root vertices use the low-link condition, not children count.\n\n---\n\n### Mistake 4: Visited Array in Bipartite Matching\n\n```java\n// ❌ WRONG: Reusing visited array across all starting vertices\nvisited = new boolean[rightSize]; // Outside loop\nfor (int u = 0; u < leftSize; u++) {\n if (dfs(u)) matching++;\n}\n\n// ✅ CORRECT: Reset visited for each starting vertex\nfor (int u = 0; u < leftSize; u++) {\n visited = new boolean[rightSize]; // Inside loop\n if (dfs(u)) matching++;\n}\n```\n\n---\n\n## 🐛 Debug This: SCC with Incorrect DFS Ordering\n\nThis Tarjan's SCC implementation has a subtle bug. Can you find it?\n\n```java\npublic class BuggyTarjanSCC {\n private Map> graph;\n private int[] ids, lowLinks;\n private boolean[] onStack;\n private Deque stack;\n private int id;\n private List> sccs;\n\n public List> findSCCs(int vertices) {\n // Initialization...\n ids = new int[vertices];\n lowLinks = new int[vertices];\n onStack = new boolean[vertices];\n stack = new ArrayDeque<>();\n sccs = new ArrayList<>();\n id = 0;\n Arrays.fill(ids, -1);\n\n for (int v = 0; v < vertices; v++) {\n if (ids[v] == -1) {\n dfs(v);\n }\n }\n return sccs;\n }\n\n private void dfs(int v) {\n ids[v] = lowLinks[v] = id++;\n stack.push(v);\n onStack[v] = true;\n\n for (int neighbor : graph.getOrDefault(v, Collections.emptyList())) {\n if (ids[neighbor] == -1) {\n dfs(neighbor);\n lowLinks[v] = Math.min(lowLinks[v], lowLinks[neighbor]);\n } else if (onStack[neighbor]) {\n // BUG IS HERE\n lowLinks[v] = Math.min(lowLinks[v], lowLinks[neighbor]);\n }\n }\n\n // Pop SCC when root found\n if (ids[v] == lowLinks[v]) {\n List component = new ArrayList<>();\n int w;\n do {\n w = stack.pop();\n onStack[w] = false;\n component.add(w);\n } while (w != v);\n sccs.add(component);\n }\n }\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: In the back edge case, using `lowLinks[neighbor]` instead of `ids[neighbor]`.\n\n```java\n// ❌ BUG: lowLinks[neighbor] may have been updated\n} else if (onStack[neighbor]) {\n lowLinks[v] = Math.min(lowLinks[v], lowLinks[neighbor]);\n}\n\n// ✅ FIX: Use ids[neighbor] (discovery time)\n} else if (onStack[neighbor]) {\n lowLinks[v] = Math.min(lowLinks[v], ids[neighbor]);\n}\n```\n\n**Why this matters**:\n\n```\nConsider graph: 0 → 1 → 2 → 0\n\nDFS from 0:\n Visit 0: id=0, low=0, stack=[0]\n Visit 1: id=1, low=1, stack=[0,1]\n Visit 2: id=2, low=2, stack=[0,1,2]\n Back edge 2→0:\n With bug: low[2] = min(2, low[0]) = min(2, 0) = 0 ✓\n Actually works here, but...\n\nConsider: 0 → 1 → 2 → 1 (where 2→1 is back edge)\n\nWith correct algorithm, when we see back edge 2→1:\n low[2] = min(low[2], id[1]) = min(2, 1) = 1\n\nBut if low[1] was updated before we return:\n The buggy version might use an outdated low[1]\n```\n\nThe fix ensures we always reference the stable discovery time, not the potentially-changing low-link value.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Find All SCCs ⭐⭐\n\nImplement both Kosaraju's and Tarjan's algorithms and verify they produce the same SCCs.\n\n```java\npublic class SCCVerifier {\n public boolean verifySame(int[][] edges, int vertices) {\n // Implement both algorithms\n // Return true if they find the same SCCs (order doesn't matter)\n }\n}\n```\n\n**Test case**:\n```\nVertices: 8\nEdges: 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 6→5, 6→7, 7→6\nExpected SCCs: {0,1,2}, {3,4,5}, {6,7}\n```\n\n---\n\n### Exercise 2: Critical Infrastructure ⭐⭐\n\nGiven a network of servers and connections, find:\n1. All articulation points (critical servers)\n2. All bridges (critical connections)\n\n```java\npublic class NetworkAnalyzer {\n public static class Analysis {\n List criticalServers;\n List criticalConnections;\n }\n\n public Analysis analyze(int servers, int[][] connections) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 3: Maximum Flow with Multiple Sources ⭐⭐⭐\n\nModify Edmonds-Karp to handle multiple sources and sinks.\n\n```java\npublic class MultiSourceMaxFlow {\n public int maxFlow(int vertices, int[][] edges,\n int[] sources, int[] sinks) {\n // Hint: Add super-source and super-sink\n }\n}\n```\n\n---\n\n### Exercise 4: Job Assignment Problem ⭐⭐⭐\n\nGiven 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).\n\n```java\npublic class JobAssignment {\n public int maxJobsCompleted(int workers, int jobs,\n List> skills) {\n // Use bipartite matching\n }\n\n // Bonus: Return the actual assignment\n public int[] getAssignment() { }\n}\n```\n\n---\n\n### Exercise 5: Minimum Vertex Cover ⭐⭐⭐⭐\n\nIn a bipartite graph, find the minimum set of vertices that covers all edges. Use König's theorem: minimum vertex cover = maximum matching.\n\n```java\npublic class MinVertexCover {\n public Set findMinVertexCover(\n int leftSize, int rightSize, List edges) {\n // 1. Find maximum matching\n // 2. Apply König's theorem construction\n }\n}\n```\n\n**Hint**: After finding max matching:\n- Start BFS from unmatched left vertices\n- Alternating between unmatched and matched edges\n- Minimum vertex cover = (matched left not reached) ∪ (right reached)\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"When would you use Tarjan's vs Kosaraju's SCC algorithm?\"\n\n**Answer**: Both have O(V+E) complexity, but differ in practice:\n\n**Tarjan's**:\n- Single DFS pass\n- Lower constant factors\n- More complex to implement correctly\n- Outputs SCCs in reverse topological order\n\n**Kosaraju's**:\n- Two DFS passes (original + reversed graph)\n- Easier to understand and implement\n- Requires building reverse graph (extra O(V+E) space)\n- More intuitive proof of correctness\n\n**Choose Tarjan's** when: memory is constrained, or you need the algorithm in competitive programming.\n\n**Choose Kosaraju's** when: clarity is important, or you're teaching/explaining SCCs.\n\n---\n\n### Q2: \"Explain the max-flow min-cut theorem and a practical application.\"\n\n**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.\n\n**Intuition**:\n- Maximum flow is limited by some bottleneck\n- That bottleneck is exactly the minimum cut\n\n**Practical application - Image Segmentation**:\n\n```\nProblem: Separate foreground from background in image\n\nModel:\n- Each pixel is a vertex\n- Source connects to \"definitely foreground\" pixels (∞ capacity)\n- Sink connects to \"definitely background\" pixels (∞ capacity)\n- Adjacent pixels connected with capacity = similarity\n\nMin-cut finds optimal boundary between foreground/background\n(minimizes cutting through similar pixels)\n```\n\n---\n\n### Q3: \"How would you find if a graph has a unique topological ordering?\"\n\n**Answer**: A DAG has a unique topological ordering if and only if there's a Hamiltonian path (path visiting all vertices exactly once).\n\n**Algorithm**:\n```java\npublic boolean hasUniqueTopologicalOrder(int vertices,\n List> adj) {\n // Use Kahn's algorithm\n int[] inDegree = new int[vertices];\n for (List neighbors : adj) {\n for (int v : neighbors) inDegree[v]++;\n }\n\n Queue queue = new LinkedList<>();\n for (int v = 0; v < vertices; v++) {\n if (inDegree[v] == 0) queue.offer(v);\n }\n\n while (!queue.isEmpty()) {\n // If queue ever has more than 1 element,\n // ordering is not unique\n if (queue.size() > 1) return false;\n\n int u = queue.poll();\n for (int v : adj.get(u)) {\n if (--inDegree[v] == 0) queue.offer(v);\n }\n }\n\n return true;\n}\n```\n\n---\n\n### Q4: \"Design a system to match drivers to riders optimally.\"\n\n**Answer**: This is a bipartite matching problem with weights (Hungarian algorithm for minimum cost).\n\n```java\npublic class RideMatching {\n // Model:\n // - Left vertices: available drivers\n // - Right vertices: ride requests\n // - Edge weight: estimated pickup time or distance\n\n public Map matchOptimally(\n List drivers, List riders) {\n\n // Build cost matrix\n int[][] cost = new int[drivers.size()][riders.size()];\n for (int d = 0; d < drivers.size(); d++) {\n for (int r = 0; r < riders.size(); r++) {\n cost[d][r] = calculatePickupTime(drivers.get(d),\n riders.get(r));\n }\n }\n\n // Hungarian algorithm for minimum cost matching\n int[] assignment = hungarianAlgorithm(cost);\n\n // Build result\n Map matching = new HashMap<>();\n for (int d = 0; d < assignment.length; d++) {\n if (assignment[d] != -1) {\n matching.put(drivers.get(d), riders.get(assignment[d]));\n }\n }\n return matching;\n }\n}\n```\n\n**Considerations**:\n- Real-time updates as drivers/riders appear\n- Batch matching every few seconds\n- Consider fairness (don't always assign closest)\n\n---\n\n### Q5: \"What's the relationship between articulation points and 2-edge-connected components?\"\n\n**Answer**:\n\n**Articulation points** split the graph into biconnected components (2-vertex-connected).\n**Bridges** split the graph into 2-edge-connected components.\n\n```\n2-vertex-connected: Remains connected after removing any single vertex\n2-edge-connected: Remains connected after removing any single edge\n\nRelationship:\n- Every bridge's endpoints are articulation points (unless degree 1)\n- Articulation point doesn't always imply bridge exists\n\nExample:\n A --- B\n | X | (X marks diagonal edges)\n C --- D\n\nNo bridges (every edge is in a cycle)\nNo articulation points (2-vertex-connected)\n\nvs:\n\n A --- B --- E\n | |\n C --- D\n\nB is articulation point\nB-E is a bridge\n```\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Complexity\n\n| Algorithm | Time | Space | Use Case |\n|-----------|------|-------|----------|\n| Kosaraju's SCC | O(V+E) | O(V+E) | Find strongly connected components |\n| Tarjan's SCC | O(V+E) | O(V) | Find SCCs, single pass |\n| Articulation Points | O(V+E) | O(V) | Find critical vertices |\n| Bridges | O(V+E) | O(V) | Find critical edges |\n| Ford-Fulkerson | O(E × max_flow) | O(V²) | Max flow (integer capacities) |\n| Edmonds-Karp | O(VE²) | O(V²) | Max flow (polynomial) |\n| Hungarian | O(V³) | O(V²) | Min cost bipartite matching |\n| Hopcroft-Karp | O(E√V) | O(V) | Max bipartite matching |\n\n### Key Formulas\n\n```\nSCC Root Condition: ids[v] == lowLinks[v]\nArticulation (root): children > 1\nArticulation (non-root): lowLinks[child] >= ids[v]\nBridge Condition: lowLinks[v] > ids[parent]\nMax-Flow = Min-Cut: Always true (duality theorem)\nKönig's Theorem: Min Vertex Cover = Max Matching (bipartite)\n```\n\n### Code Templates\n\n```java\n// Tarjan's SCC - key part\nif (ids[v] == lowLinks[v]) {\n // v is root of SCC, pop until v\n}\n\n// Articulation point check\nif (parent[u] == -1 && children > 1) isArticulation[u] = true;\nif (parent[u] != -1 && low[v] >= disc[u]) isArticulation[u] = true;\n\n// Flow augmentation\nfor (v = sink; v != source; v = parent[v]) {\n residual[parent[v]][v] -= pathFlow;\n residual[v][parent[v]] += pathFlow;\n}\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 15: Graph Algorithms in Practice**, we'll explore:\n- Social network analysis\n- Recommendation systems\n- PageRank algorithm\n- Community detection\n- Real-world case studies\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + exercises | 90 min |\n| 1 | Quick Reference + SCCs | 10 min |\n| 3 | Implement Tarjan's from memory | 20 min |\n| 7 | Max-flow problem | 15 min |\n| 14 | Debug exercise + bipartite matching | 15 min |\n| 30 | All interview questions | 10 min |\n\n---\n\n**Next**: [Part 15: Graph Algorithms in Practice →](./algorithms-part-15-graph-algorithms-in-practice.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.213891Z","createdAt","2026-06-10T07:19:25.214955Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",29,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",14,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},176,"Tarjan","tarjan",175,"Scc","scc",177,"Max Flow","max-flow",178,"Ford-fulkerson","ford-fulkerson",179,"Bipartite Matching","bipartite-matching",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]