# CS 6515 — Graph Algorithms (Exam 2) Ultimate Black-Box Cheat Sheet

All graph solutions follow the required format from Ed Post #191, using ONLY the
black boxes in #192, **unmodified**. No pseudocode. Narrative form. Always in
adjacency list; you always have n = |V| and m = |E|.

> **Modifying a black box loses full credit even if otherwise correct.** Change the
> INPUT you pass in and the OUTPUT you read out — never the algorithm's internals.

---

## Solution Format (3 Required Parts) — #191

### (a) Algorithm
- Describe HOW in words (narrative; bulleted steps OK, no pseudocode / no line-by-line).
- State how you MODIFY THE INPUT (build/reverse/subgraph/re-weight).
- Name the black box, WHAT you pass in, WHAT output you use.
- State any output modification, and **THE FINAL RETURN** (this is a common leak).

### (b) Justification of Correctness
- WHY it works, informal narrative (not a formal proof).
- **Prove BOTH directions** of any if-and-only-if (your recurring leak).
- **Name the disqualified tool** and why yours is legal (preconditions).
- **CITE why any planted guarantee matters** (no-neg-cycle, F-acyclic, one-source…).
  If the problem hands you a condition, it is load-bearing — explain its role.

### (c) Runtime Analysis
- Worst case, tightest bound, fully simplified Big-O.
- Analyze ALL steps incl. pre/post-processing; cite black-box runtimes as-is.
- Tightest bound: O(n+m) is NOT O(n²); tree (m=n-1) collapses O(n+m) → O(n).

---

## The 5-Point Self-Check (run before you call any problem done)
1. Did I state **(a)/(b)/(c)** as labeled parts, and state **the RETURN**?
2. Did I **name the right object**? (source vs sink, edge vs vertex, cost vs path,
   rate vs weight, weight vs hops, task-time vs edge-cost)
3. Does **(b) prove BOTH directions**, and does it **match (a)** (same operation)?
4. Did I **name the disqualified tool** + **cite why the given guarantee matters**?
5. Is the runtime the **tightest simplified** bound, accounting for preprocessing?

---

## Runtime Rapid-Fire

| Black box | Runtime |
|---|---|
| DFS, BFS, Topological Sort, SCC, 2-SAT | O(n + m) |
| Dijkstra | O((n + m) log n) |
| Bellman-Ford | O(nm) |
| Floyd-Warshall | O(n³) |
| Kruskal, Prim | O(m log n) |
| Ford-Fulkerson | O(mC)  (C = max-flow value; NOT poly) |
| Edmonds-Karp | O(nm²)  (polynomial, capacity-independent) |

Common ops (#8): traverse/reverse/copy/subgraph = O(n+m); one edge (u,v) = O(n)
(scan u's list); vertex/edge property (weight,color,capacity) = O(1) once you hold it.
Σ(out-degrees) = m → "scan every adjacency list once" = O(n+m), NOT O(n·something).

---

## Preconditions (deduction magnets)

| Requirement | Black boxes |
|---|---|
| Needs a **DAG** | Topological Sort |
| Needs a **directed** graph | SCC, 2-SAT, Topo Sort, Flows (FF/EK) |
| Needs **connected undirected** | Kruskal, Prim (MST) |
| **Non-negative** weights only | Dijkstra |
| Handles **negative** weights | Bellman-Ford, Floyd-Warshall |
| Detects a **negative cycle** | Bellman-Ford, Floyd-Warshall |
| **Positive integer** capacities | Ford-Fulkerson |

---

## The 12 Black Boxes

### DFS — O(n+m)
In: simple graph (+ optional start). Out: ccnum[], prev[], pre[], post[].
Uses: connected components, cycle detection (back edge), path to a reachable vertex.
Key facts: cycle ⟺ a back edge (edge (u,v) with [pre,post] of u nested in v's).
Topological order = vertices by DECREASING post.

### Topological Sort — O(n+m)
In: DAG. Out: order[] (source→sink) + DFS outputs.
Uses: prerequisite ordering; the backbone of DAG dynamic programming.

### SCC — O(n+m)
In: directed graph. Out: metagraph (a DAG, components in REVERSE topo order sink→source)
+ DFS outputs. Uses: collapse cycles → DAG; find source/sink components.
- "Reaches everyone" (mother vertex, universal reacher) → **SOURCE** SCC.
- "Reached BY everyone" (everyone can reach it) → **SINK** SCC.
- Whole graph strongly connected ⟺ exactly ONE component.

### BFS — O(n+m)
In: simple graph + start. Out: dist[] (UNWEIGHTED = #edges; ∞ if unreachable), prev[].
Uses: unweighted shortest path, reachability, bipartite/2-color check.

### Dijkstra — O((n+m) log n)
In: graph + start + NON-NEGATIVE weights. Out: dist[] (weighted), prev[].
Uses: weighted shortest path, no negative edges. Illegal the instant an edge is negative.

### Bellman-Ford — O(nm)
In: graph + start + weights (negatives OK). Out: dist[], prev[], iter[][] (dist after k edges).
Uses: shortest path WITH negatives; negative-cycle detection.
For "negative cycle ANYWHERE": add a super-source with 0-weight edges to all vertices.

### Floyd-Warshall — O(n³)
In: graph + weights. Out: dist[u][v] (ALL PAIRS), iter[][][]. 
Uses: all-pairs shortest paths; negative-cycle detection; **shortest cycle** (min over edges
of w(u,v)+dist[v][u]).

### Kruskal — O(m log n)
In: connected undirected + weights. Out: edges[] = the n-1 MST edges (edge list).

### Prim — O(m log n)
In: connected undirected + weights. Out: prev[] = MST edges (parent pointers).

### Ford-Fulkerson — O(mC)
In: connected directed + POSITIVE INTEGER capacities + s + t. Out: flow[], C = max-flow value.
Best when capacities/flow value are small integers (C bounded).

### Edmonds-Karp — O(nm²)
In: connected directed + positive capacities + s + t. Out: flow[], C.
Cite this for a clean polynomial, capacity-independent runtime.

### 2-SAT — O(n+m)
In: CNF, ≤2 literals/clause (n vars, m clauses). Out: assignments[] or "NO" (+ SCC outputs).
Build: clause (a∨b) → edges (¬a→b) and (¬b→a). Run SCC.
UNSAT ⟺ some x and ¬x share an SCC.

---

## Trigger Table (problem shape → tool)

| The problem asks… | Reach for |
|---|---|
| Shortest path / fewest edges, UNWEIGHTED | BFS |
| Shortest path, NON-NEGATIVE weights | Dijkstra |
| Shortest path with NEGATIVE edges / detect neg cycle | Bellman-Ford |
| ALL-PAIRS shortest paths / shortest cycle | Floyd-Warshall |
| Order tasks w/ prerequisites; DAG longest/weighted path | Topo Sort + DP |
| Everyone reaches everyone? | SCC, count == 1 |
| A vertex/cluster that REACHES all | SCC → source component |
| A vertex/cluster REACHED BY all | SCC → sink component |
| Cycle exists? / connected components | DFS |
| Binary choices with if-A-then-B / at-most-one constraints | 2-SAT |
| Connect all nodes at min cost | MST (Kruskal/Prim) |
| Prefer one edge TYPE unless forced | MST + two-tier weights |
| Force specific edges into the tree | Zero them, run Kruskal (needs F acyclic) |
| Max throughput / matching / disjoint paths / route k units | Max flow (FF/EK) |
| Min cut / cheapest edges to disconnect s–t | Max flow = min cut |
| Bipartite / 2-colorable? | BFS (layer parity) |

---

## Reduction Meta-Patterns (the reusable moves)

**MAXIMIZE with a min-only tool → transform.**
- Maximize a PRODUCT (currency rates) → weight = −log(r), Bellman-Ford (logs go negative).
- Maximize a SUM → negate weights, run BF, negate the answer back.
- The planted cycle guarantee is always about the TRANSFORMED graph
  (no-positive-cycle → no-negative-cycle after negation).

**Constrained path (order/structure matters) → LAYERED graph.**
- One copy of all vertices per "phase"; within-layer edges = allowed moves;
  forward-only edges between layers = allowed transitions. Plain BFS/DFS from
  s in start layer; check t in valid end layer. (HW5 red/black; "must pass a shop".)
- Contraction (SCC) only preserves REACHABILITY; use layering when the constraint
  is about the path's structure — UNLESS you've encoded the constraint into edge
  DIRECTIONS first, then SCC-contract is safe.

**"Must stop at one of a set" / "best modification among k options" → precompute both ends.**
- Dijkstra from s on G, Dijkstra from t on G^R; evaluate each candidate in O(1)
  as dist_s[x] + (bonus/edge) + dist_t[x]. (4.20 new road; Tim's Coffee.)

**Reverse graph (G^R) trick.**
- "Can v reach T?" for all v → run from T on G^R ("T reaches v" in G^R = "v reaches T" in G).
- Build G^R in O(n+m): for each edge u→v, append u to row v.

**Reachability: which tool?**
- Single-source ("can u reach v") → BFS/DFS.
- All-pairs / structural ("does everyone reach everyone") → SCC.
- If "BFS from every vertex" busts the runtime budget → you need the structural tool.

---

## FLOW MODELING (build the network; the black box is the easy part)

**Core rule: every "at most k of X" constraint → an edge of capacity k.**
Integer capacities → integer flow → each cap-1 edge is a clean yes/no decision.
Source/sink are artificial (add them), but their EDGES carry the constraints.
**Always translate the max-flow VALUE back into the problem's terms.**

**Bipartite matching template:**
- s → each Left, cap 1  ("each left used at most once")
- each Right → t, cap 1  ("each right used at most once")
- Left → Right, cap 1, ONLY for legal pairings
- Max flow = size of maximum matching.

**Gadgets:**
- Multiple sources/sinks → add super-source S → each sᵢ (cap ∞), each tᵢ → super-sink T (cap ∞).
- Vertex capacity (limit flow THROUGH v) → split v into v_in → v_out, cap = the vertex limit;
  all in-edges to v_in, all out-edges from v_out.
- Cap TOTAL usage at C → funnel all "used" flow through one bottleneck edge of capacity C.
- One resource covers many items (camera covers row+col) → make the ITEMS the flow units.

**FF vs EK:** small/bounded C → FF O(mC) is great (state "C ≤ …"). Otherwise EK O(nm²).
**Discipline:** yes/no or count question → read the VALUE. Don't recover the cut/cover/
partition (residual BFS, König min-cut) unless the problem explicitly asks — that risks
"modified black box." (König: max matching = min vertex cover — keep as intuition, don't cite.)

---

## MST Property Facts (for MC + justifications)

- **Cut property:** the min-weight edge across ANY cut is in some MST.
- **Cycle property:** the max-weight edge on ANY cycle is in NO MST.
- Distinct weights ⟹ the MST is UNIQUE.
- The globally minimum-weight edge is always in the MST.
- The max-weight edge is NOT always excluded — a bridge must be in every spanning tree.
- **Minimax / bottleneck:** the MST path between s,t minimizes the maximum edge on the path.

---

## DFS Edge-Type Facts (for MC)

- Tree edge: to a brand-new vertex (parent→child). Back edge: to an ancestor still open
  (post(u) < post(v)). Forward edge: to a descendant already finished. Cross edge:
  everything else (pre(u) > pre(v) and post(u) > post(v) → cross).
- Undirected DFS has only TREE and BACK edges.

---

## Given-Guarantee Reflex (your signature Exam-2 leak)
When the problem hands you a condition, ask "why did they give me this?" — it's load-bearing,
and (b) MUST cite its role:
- "No negative cycle" → shortest paths well-defined → Bellman-Ford valid.
- "No positive-profit cycle" → after negation, no negative cycle → BF valid.
- "F is acyclic" → forced 0-weight edges never rejected by Kruskal → all of F included.
- "Exactly one source/sink" → the metagraph source/sink is unique.
- "DAG guaranteed" → topological sort is valid → the DP recurrence is well-defined.