Graph Algorithms — Shortest Paths, MST & Union-Find

Chapter 19 · Part 4: ALGORITHMS · Est. 25 min read

Chapter Goal: Master the four pillars of advanced graph algorithms — Dijkstra (greedy shortest path), Bellman-Ford (negative weights), Floyd-Warshall (all-pairs), and Union-Find (the most versatile 5-line data structure in competitive programming). Then apply them to Minimum Spanning Trees via Kruskal's and Prim's. These algorithms power routing, networking, scheduling, and clustering — all FAANG-heavy domains.

19.1 Dijkstra's Algorithm — Single-Source Shortest Path

Core Idea

Dijkstra's is a greedy algorithm. At each step, it picks the unvisited vertex with the smallest known distance, finalizes its distance, and relaxes its outgoing edges.

Critical requirement: All edge weights must be non-negative.

Why negative weights break Dijkstra:
  A -- 10 -- B
  |          |
  1         -15
  |          |
  C ------- D

dist[B] finalized as 10 (via A→B).
Later: A→C→D→B has cost 1 + (−15) = −14, which is better.
But B is already finalized! Dijkstra CANNOT go back.
→ Use Bellman-Ford for negative weights.

Implementation with Priority Queue

vector<long long> dijkstra(int start, int n,
                            vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)}
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> minPQ;  // {distance, node}
 
    dist[start] = 0;
    minPQ.push({0, start});
 
    while (!minPQ.empty()) {
        auto [d, u] = minPQ.top(); minPQ.pop();
 
        // Lazy deletion: skip stale entries
        if (d > dist[u]) continue;
 
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                minPQ.push({dist[v], v});
            }
        }
    }
    return dist;
}
// Time:  O((V + E) log V)
// Space: O(V + E)
// dist[v] = shortest distance from start to v (LLONG_MAX if unreachable)

Stale Entry Handling — Critical Detail

// Without lazy deletion, old {large_dist, v} entries stay in the queue.
// When we later pop them, dist[v] may already be finalized as a smaller value.
// The check "if (d > dist[u]) continue" skips these stale entries.
 
// Example:
// Push {10, B} for path A→B
// Find shorter path A→C→B = 5, push {5, B}
// Queue: [{5,B}, {10,B}]
// Pop {5,B}: process B (dist[B]=5 finalized)
// Pop {10,B}: d=10 > dist[B]=5 → SKIP (stale)

Path Reconstruction

vector<long long> dijkstraWithPath(int start, int n,
                                    vector<vector<pair<int,int>>>& adj,
                                    vector<int>& prev) {
    vector<long long> dist(n, LLONG_MAX);
    prev.assign(n, -1);  // prev[v] = node before v on shortest path
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
 
    dist[start] = 0;
    pq.push({0, start});
 
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;            // Record path
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
 
// Reconstruct path from start to end:
vector<int> getPath(vector<int>& prev, int end) {
    vector<int> path;
    for (int v = end; v != -1; v = prev[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

Dijkstra on a Grid

// Minimum cost path on a weighted grid (e.g., LC 1631 Path With Min Effort)
int dijkstraGrid(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>,
                   greater<>> pq;  // {cost, row, col}
 
    dist[0][0] = 0;
    pq.push({0, 0, 0});
 
    while (!pq.empty()) {
        auto [cost, r, c] = pq.top(); pq.pop();
        if (cost > dist[r][c]) continue;
        if (r == R-1 && c == C-1) return cost;
 
        for (int d = 0; d < 4; d++) {
            int nr = r+dx[d], nc = c+dy[d];
            if (nr<0||nr>=R||nc<0||nc>=C) continue;
            int newCost = max(cost, abs(grid[nr][nc]-grid[r][c]));
            if (newCost < dist[nr][nc]) {
                dist[nr][nc] = newCost;
                pq.push({newCost, nr, nc});
            }
        }
    }
    return dist[R-1][C-1];
}

19.2 Bellman-Ford — Negative Weights & Cycle Detection

Relax all edges V-1 times. After k iterations, we have the correct shortest paths using at most k edges. Since any simple path has at most V-1 edges, V-1 iterations suffice for graphs without negative cycles.

Works with negative edge weights. Detects negative cycles.

Key insight: After k rounds of relaxing all edges,
dist[v] = shortest path from source to v using at most k edges.
After V-1 rounds: shortest paths (simple paths) are finalized.
If V-th round still updates any distance → negative cycle exists.

vector<long long> bellmanFord(int start, int n,
                               vector<tuple<int,int,int>>& edges) {
    // edges = {u, v, weight} (directed)
    vector<long long> dist(n, LLONG_MAX);
    dist[start] = 0;
 
    // V-1 relaxation rounds
    for (int round = 0; round < n-1; round++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // Early termination: already converged
    }
 
    // Negative cycle detection: V-th round
    for (auto [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            // This edge can still be relaxed → negative cycle!
            return {};  // Signal: negative cycle exists
        }
    }
    return dist;
}
// Time:  O(V × E)
// Space: O(V)

Bellman-Ford with K Relaxations (Cheapest Flights)

// LC 787: Find shortest path from src to dst using at most k+1 edges
vector<int> cheapestFlightsKStops(int n, vector<vector<int>>& flights,
                                   int src, int dst, int k) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
 
    // k+1 edges = k stops in between → k+1 relaxation rounds
    for (int i = 0; i <= k; i++) {
        vector<long long> temp = dist;  // Use previous round's values!
        for (auto& f : flights) {
            int u=f[0], v=f[1], w=f[2];
            if (dist[u] != LLONG_MAX && dist[u]+w < temp[v]) {
                temp[v] = dist[u] + w;
            }
        }
        dist = temp;
    }
    return dist[dst] == LLONG_MAX ? -1 : dist[dst];
}
// Time: O(k × E), Space: O(V)
// Critical: copy dist to temp before each round to prevent using updates
// from the SAME round (would allow more than i edges)

19.3 Floyd-Warshall — All-Pairs Shortest Path

Core Idea

Dynamic programming: dist[i][j] = shortest path from i to j using intermediate vertices from the set {0, 1, ..., k}.

State transition:
dist[i][j] = min(dist[i][j],      ← path not through k
                 dist[i][k] + dist[k][j])  ← path through k

k must be the OUTERMOST loop (process all i,j pairs for each k)

void floydWarshall(int n, vector<vector<long long>>& dist) {
    // dist[i][j] should be initialized to:
    //   0          if i == j
    //   weight     if edge (i,j) exists
    //   LLONG_MAX/2 otherwise (use /2 to avoid overflow in addition)
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    // After: dist[i][j] = shortest path from i to j (or LLONG_MAX/2 if unreachable)
    // Negative cycle: if dist[i][i] < 0 for any i
}
 
// Build the distance matrix from edge list:
vector<vector<long long>> buildFloydMatrix(int n,
                                            vector<tuple<int,int,int>>& edges) {
    const long long INF = 1e18;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto [u, v, w] : edges) {
        dist[u][v] = min(dist[u][v], (long long)w);
        // For undirected: also dist[v][u] = min(dist[v][u], w)
    }
    floydWarshall(n, dist);
    return dist;
}
// Time:  O(V³)
// Space: O(V²)
// Use when: V ≤ ~400 (400³ = 64M ops, feasible)
//           Need all-pairs distances
//           Graph may have negative edges (but no negative cycles)

Floyd-Warshall Applications

// Find the city with fewest reachable neighbors within threshold (LC 1334)
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    vector<vector<long long>> dist(n, vector<long long>(n, 1e9));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto& e : edges) {
        dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];
    }
    for (int k=0;k<n;k++) for (int i=0;i<n;i++) for (int j=0;j<n;j++)
        dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
 
    int ans = -1, minCount = n+1;
    for (int i = n-1; i >= 0; i--) {  // Prefer larger city index on tie
        int count = 0;
        for (int j = 0; j < n; j++)
            if (i != j && dist[i][j] <= distanceThreshold) count++;
        if (count <= minCount) { minCount = count; ans = i; }
    }
    return ans;
}

19.4 Union-Find / Disjoint Set Union (DSU)

DSU maintains a collection of disjoint sets and supports two operations:

find(x): which set does x belong to? (returns the root/representative)
union(x, y): merge the sets containing x and y

Full Implementation with Path Compression & Union by Rank

class DSU {
    vector<int> parent, rank_;
    int components;
 
public:
    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i initially
    }
 
    // Find with PATH COMPRESSION: make every node on the path point to root
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // Recursive path compression
        return parent[x];
    }
 
    // Union by RANK: attach smaller-rank tree under larger-rank tree
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // Already in same set
 
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;             // Attach ry's tree under rx
        if (rank_[rx] == rank_[ry]) rank_[rx]++;  // Only increase if equal
        components--;
        return true;  // Successfully merged
    }
 
    bool connected(int x, int y) { return find(x) == find(y); }
    int  numComponents()          { return components; }
};
// find: O(α(n)) amortized ≈ O(1)    (inverse Ackermann — grows incredibly slowly)
// unite: O(α(n)) amortized ≈ O(1)
// Space: O(n)

Path Compression — Visual

Before find(7):          After find(7):
    1                        1
   / \                    / | \ \
  3   2                  3  2  7  (7 and others now point directly to root 1)
  |   |
  5   4
  |
  7

Without compression: find(7) = O(depth)
With compression:    next find(7) = O(1)

Union by Size (Alternative to Union by Rank)

// More intuitive: always attach smaller set under larger set
class DSU_Size {
    vector<int> parent, size_;
    int components;
public:
    DSU_Size(int n) : parent(n), size_(n, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size_[rx] < size_[ry]) swap(rx, ry);
        parent[ry] = rx;
        size_[rx] += size_[ry];
        components--;
        return true;
    }
    int  getSize(int x)   { return size_[find(x)]; }
    bool connected(int x, int y) { return find(x) == find(y); }
    int  numComponents()  { return components; }
};

DSU Applications

// 1. Cycle detection in undirected graph
bool hasCycleDSU(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) {
        if (!dsu.unite(u, v)) return true;  // Already connected → cycle!
    }
    return false;
}
 
// 2. Count connected components
int countComponents(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) dsu.unite(u, v);
    return dsu.numComponents();
}
 
// 3. Dynamic connectivity (add edges, check connectivity)
DSU dsu(n);
dsu.unite(0, 1);
dsu.unite(2, 3);
dsu.connected(0, 2);  // false — different components
dsu.unite(1, 2);
dsu.connected(0, 3);  // true — now all connected

19.5 Kruskal's Algorithm — MST via Edge Sorting

Core Idea

Sort all edges by weight. Process in ascending order — add an edge to the MST only if it connects two different components (doesn't create a cycle). Stop when n-1 edges are added.

Greedy correctness: Adding the globally cheapest safe edge (one that doesn't
form a cycle) always leads to a minimum spanning tree (Cut Property).

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const { return weight < other.weight; }
};
 
pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());   // Sort by weight ascending
 
    DSU dsu(n);
    long long totalWeight = 0;
    vector<Edge> mstEdges;
 
    for (auto& edge : edges) {
        if (dsu.unite(edge.u, edge.v)) {   // If different components
            mstEdges.push_back(edge);
            totalWeight += edge.weight;
            if ((int)mstEdges.size() == n-1) break;  // MST complete
        }
    }
 
    // If mstEdges.size() < n-1: graph is not connected → no MST
    return {totalWeight, mstEdges};
}
// Time:  O(E log E) for sorting + O(E α(V)) for DSU = O(E log E)
// Space: O(E) for edges + O(V) for DSU

Kruskal's for Minimum Cost to Connect All Points

// LC 1584: Points on a 2D plane, edge weight = Manhattan distance
int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<Edge> edges;
 
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int w = abs(points[i][0]-points[j][0])
                  + abs(points[i][1]-points[j][1]);
            edges.push_back({i, j, w});
        }
 
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long cost = 0;
    int edgeCount = 0;
 
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            cost += e.weight;
            if (++edgeCount == n-1) break;
        }
    }
    return cost;
}
// Time: O(n² log n) — n² edges, sort + DSU

19.6 Prim's Algorithm — MST via Vertex Growing

Core Idea

Start from any vertex. Maintain a priority queue of edges crossing the "tree boundary" (one endpoint in MST, one outside). Always pick the cheapest.

Unlike Kruskal's (global edge view), Prim's grows the MST locally —
like BFS but with a priority queue instead of a regular queue.

long long prims(int start, int n,
                vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)}
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<>> minPQ;  // {weight, vertex}
 
    minPQ.push({0, start});
    long long totalWeight = 0;
    int edgesAdded = 0;
 
    while (!minPQ.empty() && edgesAdded < n) {
        auto [w, u] = minPQ.top(); minPQ.pop();
        if (inMST[u]) continue;   // Already in MST
 
        inMST[u] = true;
        totalWeight += w;
        edgesAdded++;
 
        for (auto [v, weight] : adj[u]) {
            if (!inMST[v]) {
                minPQ.push({weight, v});
            }
        }
    }
    return totalWeight;
}
// Time:  O((V + E) log V) with binary heap
// Space: O(V + E)

Kruskal's vs. Prim's Comparison

Aspect	Kruskal's	Prim's
Approach	Edge-based (global)	Vertex-based (local)
Key structure	DSU	Priority Queue
Best for	Sparse graphs (E ≈ V)	Dense graphs (E ≈ V²)
Time	O(E log E)	O(E log V)
Handles disconnected	(no MST)	(no MST)
Easier to implement	Slightly	Slightly harder

19.7 Algorithm Decision Guide

SHORTEST PATH PROBLEMS:
│
├── Single source, non-negative weights?
│   └── DIJKSTRA — O((V+E) log V)
│       Use when: road maps, network routing
│
├── Single source, negative weights (no negative cycles)?
│   └── BELLMAN-FORD — O(V×E)
│       Use when: currency exchange rates, arbitrage detection
│
├── Single source, negative weights WITH negative cycle detection?
│   └── BELLMAN-FORD — check if Vth round updates anything
│
├── All pairs, small V (≤ 400)?
│   └── FLOYD-WARSHALL — O(V³)
│       Use when: find all pairwise distances, transitive closure
│
├── Single source, limited number of edges (k stops)?
│   └── BELLMAN-FORD (k rounds) — O(k × E)
│
└── Unweighted graph (all edges weight 1)?
    └── BFS — O(V+E) — always prefer over Dijkstra for unweighted

CONNECTIVITY PROBLEMS:
│
├── Dynamic: add edges, check connectivity?
│   └── DSU — O(α(n)) per operation
│
├── Count connected components?
│   └── DSU or DFS/BFS — O(V+E)
│
└── Detect cycle in undirected graph?
    └── DSU — O(E α(V))

MINIMUM SPANNING TREE:
│
├── Sparse graph (E ≈ V)?
│   └── KRUSKAL'S — O(E log E)
│
└── Dense graph (E ≈ V²)?
    └── PRIM'S — O(E log V) with binary heap, O(V²) with adjacency matrix

Complexity Summary

Algorithm	Time	Space	Negative Weights	Negative Cycles
Dijkstra	O((V+E) log V)	O(V+E)	No	No
Bellman-Ford	O(V×E)	O(V)	Yes	Detects
Floyd-Warshall	O(V³)	O(V²)	Yes	Detects (dist[i][i]<0)
BFS (unweighted)	O(V+E)	O(V)	N/A	N/A
DSU (find/union)	O(α(n))	O(V)	N/A	N/A
Kruskal's	O(E log E)	O(V+E)	(MST)	N/A
Prim's	O((V+E) log V)	O(V+E)	(MST)	N/A

19.8 Sample Problems

Problem 1 — Network Delay Time (Medium) — LC 743

Find the time for all nodes to receive a signal from source k. Return -1 if not possible.

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int,int>>> adj(n+1);
    for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
 
    vector<long long> dist(n+1, LLONG_MAX);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    dist[k] = 0; pq.push({0, k});
 
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u]+w < dist[v]) {
                dist[v] = dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    }
    long long ans = *max_element(dist.begin()+1, dist.end());
    return ans == LLONG_MAX ? -1 : ans;
}
// Time: O((V+E) log V), Space: O(V+E)

Problem 2 — Cheapest Flights Within K Stops (Medium) — LC 787

int findCheapestPrice(int n, vector<vector<int>>& flights,
                      int src, int dst, int k) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
 
    for (int i = 0; i <= k; i++) {
        vector<long long> temp = dist;
        for (auto& f : flights) {
            int u=f[0], v=f[1], w=f[2];
            if (dist[u]!=LLONG_MAX && dist[u]+w < temp[v])
                temp[v] = dist[u]+w;
        }
        dist = temp;
    }
    return dist[dst]==LLONG_MAX ? -1 : (int)dist[dst];
}
// Time: O(k × E), Space: O(V)
// Bellman-Ford with exactly k+1 rounds (k stops = k+1 edges)

Problem 3 — Path With Minimum Effort (Medium) — LC 1631

Find a path from top-left to bottom-right minimizing the maximum absolute difference between consecutive cells.

int minimumEffortPath(vector<vector<int>>& heights) {
    int R=heights.size(), C=heights[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>,
                   greater<>> pq;
    dist[0][0]=0; pq.push({0,0,0});
 
    while (!pq.empty()) {
        auto [effort,r,c] = pq.top(); pq.pop();
        if (effort > dist[r][c]) continue;
        if (r==R-1&&c==C-1) return effort;
        for (int d=0;d<4;d++) {
            int nr=r+dx[d], nc=c+dy[d];
            if (nr<0||nr>=R||nc<0||nc>=C) continue;
            int newEffort = max(effort, abs(heights[nr][nc]-heights[r][c]));
            if (newEffort < dist[nr][nc]) {
                dist[nr][nc]=newEffort;
                pq.push({newEffort,nr,nc});
            }
        }
    }
    return 0;
}
// Time: O(R×C×log(R×C)), Space: O(R×C)

Problem 4 — Path With Maximum Probability (Medium) — LC 1514

Find the path with maximum probability of success from start to end.

double maxProbability(int n, vector<vector<int>>& edges,
                      vector<double>& succProb, int start, int end) {
    vector<vector<pair<int,double>>> adj(n);
    for (int i=0;i<(int)edges.size();i++) {
        adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
        adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
    }
 
    vector<double> prob(n, 0.0);
    priority_queue<pair<double,int>> maxPQ;  // Max probability on top
    prob[start] = 1.0;
    maxPQ.push({1.0, start});
 
    while (!maxPQ.empty()) {
        auto [p, u] = maxPQ.top(); maxPQ.pop();
        if (p < prob[u]) continue;
        if (u == end) return p;
        for (auto [v, w] : adj[u]) {
            if (prob[u]*w > prob[v]) {
                prob[v] = prob[u]*w;
                maxPQ.push({prob[v], v});
            }
        }
    }
    return 0.0;
}
// Dijkstra variant: max probability instead of min distance
// Time: O((V+E) log V), Space: O(V+E)

Problem 5 — Find the City With Smallest Number of Neighbors (Medium) — LC 1334

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    vector<vector<long long>> dist(n, vector<long long>(n, 1e9));
    for (int i=0;i<n;i++) dist[i][i]=0;
    for (auto& e:edges) {
        dist[e[0]][e[1]]=dist[e[1]][e[0]]=e[2];
    }
    for (int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
 
    int ans=-1, minCnt=n+1;
    for (int i=n-1;i>=0;i--) {  // Largest index breaks ties
        int cnt=0;
        for (int j=0;j<n;j++) if(i!=j&&dist[i][j]<=distanceThreshold) cnt++;
        if (cnt<=minCnt) { minCnt=cnt; ans=i; }
    }
    return ans;
}
// Time: O(n³) Floyd-Warshall + O(n²) scan, Space: O(n²)

Problem 6 — Number of Connected Components (Medium) — LC 323

int countComponents(int n, vector<vector<int>>& edges) {
    DSU dsu(n);
    for (auto& e : edges) dsu.unite(e[0], e[1]);
    return dsu.numComponents();
}
// Time: O(E α(V)), Space: O(V)

Problem 7 — Redundant Connection (Medium) — LC 684

Find the edge that creates a cycle — removing it makes the graph a tree.

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    DSU dsu(n+1);  // 1-indexed
    for (auto& e : edges) {
        if (!dsu.unite(e[0], e[1])) return e;  // Already connected → redundant!
    }
    return {};
}
// Time: O(E α(V)), Space: O(V)

Problem 8 — Accounts Merge (Medium) — LC 721

Merge accounts that share at least one email address.

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, int> emailToIdx;
    DSU dsu(accounts.size());
 
    for (int i = 0; i < (int)accounts.size(); i++) {
        for (int j = 1; j < (int)accounts[i].size(); j++) {
            const string& email = accounts[i][j];
            if (emailToIdx.count(email)) {
                dsu.unite(i, emailToIdx[email]);  // Same email → same account
            } else {
                emailToIdx[email] = i;
            }
        }
    }
 
    // Group emails by their root account
    unordered_map<int, set<string>> groups;
    for (auto& [email, idx] : emailToIdx)
        groups[dsu.find(idx)].insert(email);
 
    vector<vector<string>> result;
    for (auto& [root, emails] : groups) {
        vector<string> merged = {accounts[root][0]};  // Name
        merged.insert(merged.end(), emails.begin(), emails.end());
        result.push_back(merged);
    }
    return result;
}
// Time: O(N×K×α(N×K)) where N=accounts, K=max emails per account

Problem 9 — Min Cost to Connect All Points (Medium) — LC 1584

int minCostConnectPoints(vector<vector<int>>& pts) {
    int n=pts.size();
    // Prim's: O(n² log n) — better than Kruskal's O(n² log n²) for dense graphs
    vector<int> minDist(n, INT_MAX);
    vector<bool> inMST(n, false);
    minDist[0] = 0;
    long long cost = 0;
 
    for (int iter = 0; iter < n; iter++) {
        // Find nearest non-MST node
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!inMST[i] && (u==-1 || minDist[i]<minDist[u])) u=i;
 
        inMST[u] = true;
        cost += minDist[u];
 
        // Update distances to remaining nodes
        for (int v = 0; v < n; v++) {
            if (!inMST[v]) {
                int d = abs(pts[u][0]-pts[v][0]) + abs(pts[u][1]-pts[v][1]);
                minDist[v] = min(minDist[v], d);
            }
        }
    }
    return cost;
}
// Time: O(n²) — dense graph, adjacency matrix Prim's
// Kruskal's would be O(n² log n) due to sorting all n² edges

Problem 10 — Swim in Rising Water (Hard) — LC 778

You can swim when water level ≥ cell value. Find minimum time to reach bottom-right.

int swimInWater(vector<vector<int>>& grid) {
    int n=grid.size();
    // Dijkstra: cost of path = maximum grid value along path
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>, greater<>> pq;
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    dist[0][0]=grid[0][0]; pq.push({grid[0][0],0,0});
 
    while (!pq.empty()) {
        auto [t,r,c]=pq.top();pq.pop();
        if (t>dist[r][c]) continue;
        if (r==n-1&&c==n-1) return t;
        for (int d=0;d<4;d++) {
            int nr=r+dx[d],nc=c+dy[d];
            if (nr<0||nr>=n||nc<0||nc>=n) continue;
            int nt=max(t,grid[nr][nc]);
            if (nt<dist[nr][nc]){dist[nr][nc]=nt;pq.push({nt,nr,nc});}
        }
    }
    return dist[n-1][n-1];
}
// Time: O(n² log n), Space: O(n²)

Problem 11 — Evaluate Division (Medium) — LC 399

Given equations a/b = k, find values of other divisions.

// Model as weighted graph: a → b with weight k, b → a with weight 1/k
// Query c/d = shortest multiplicative path from c to d
vector<double> calcEquation(vector<vector<string>>& equations,
                             vector<double>& values,
                             vector<vector<string>>& queries) {
    unordered_map<string, vector<pair<string,double>>> adj;
 
    for (int i = 0; i < (int)equations.size(); i++) {
        auto& a = equations[i][0], &b = equations[i][1];
        adj[a].push_back({b, values[i]});
        adj[b].push_back({a, 1.0/values[i]});
    }
 
    auto bfs = [&](const string& src, const string& dst) -> double {
        if (!adj.count(src)||!adj.count(dst)) return -1.0;
        if (src==dst) return 1.0;
        unordered_map<string,double> visited;
        queue<pair<string,double>> q;
        q.push({src, 1.0});
        visited[src] = 1.0;
        while (!q.empty()) {
            auto [u, prod] = q.front(); q.pop();
            for (auto [v, w] : adj[u]) {
                if (!visited.count(v)) {
                    double newProd = prod * w;
                    if (v == dst) return newProd;
                    visited[v] = newProd;
                    q.push({v, newProd});
                }
            }
        }
        return -1.0;
    };
 
    vector<double> result;
    for (auto& q : queries) result.push_back(bfs(q[0], q[1]));
    return result;
}
// Time: O((E + Q) × V), Space: O(V + E)

Problem 12 — Checking Existence of Edge Length Limited Paths (Hard) — LC 1697

For each query (u, v, limit): does there exist a path from u to v where ALL edge weights are strictly less than limit?

// Offline approach: sort queries and edges by limit/weight
// Process in order, adding edges that are < current limit, check connectivity
vector<bool> distanceLimitedPathsExist(int n,
    vector<vector<int>>& edgeList,
    vector<vector<int>>& queries) {
 
    // Sort edges by weight
    sort(edgeList.begin(), edgeList.end(),
         [](auto& a, auto& b){ return a[2] < b[2]; });
 
    // Sort queries by limit, keep original index
    int q = queries.size();
    vector<int> qIdx(q);
    iota(qIdx.begin(), qIdx.end(), 0);
    sort(qIdx.begin(), qIdx.end(),
         [&](int a, int b){ return queries[a][2] < queries[b][2]; });
 
    DSU dsu(n);
    int ei = 0;
    vector<bool> result(q);
 
    for (int qi : qIdx) {
        int u=queries[qi][0], v=queries[qi][1], limit=queries[qi][2];
 
        // Add all edges with weight < limit
        while (ei < (int)edgeList.size() && edgeList[ei][2] < limit) {
            dsu.unite(edgeList[ei][0], edgeList[ei][1]);
            ei++;
        }
 
        result[qi] = dsu.connected(u, v);
    }
    return result;
}
// Time: O((E + Q) log(E + Q)), Space: O(V + Q)

19.9 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Network Delay Time	Medium	Dijkstra's single-source	LC 743
2	Cheapest Flights Within K Stops	Medium	Bellman-Ford (k rounds)	LC 787
3	Path With Minimum Effort	Medium	Dijkstra on grid (max cost)	LC 1631
4	Redundant Connection	Medium	DSU cycle detection	LC 684
5	Accounts Merge	Medium	DSU grouping by shared element	LC 721
6	Min Cost to Connect All Points	Medium	Prim's MST (dense graph)	LC 1584
7	Swim in Rising Water	Hard	Dijkstra (min of max along path)	LC 778
8	Edge Length Limited Paths	Hard	Offline DSU + sorted queries	LC 1697

Suggested order: #1 (Network Delay) — Dijkstra template. #2 (Cheapest Flights) — Bellman-Ford with k constraint. #3 (Min Effort) — Dijkstra on grid. #4 (Redundant Connection) — DSU in 3 lines. #5 (Accounts Merge) — DSU for grouping. #6 (Connect Points) — Prim's dense MST. #7 and #8 are hard applications — Swim in Water (min-max Dijkstra) and Edge Limited Paths (offline DSU) are both interview classics.

Graph Algorithms — Shortest Paths, MST & Union-Find

Chapter 19 · Part 4: ALGORITHMS · Est. 25 min read

Chapter Goal: Master the four pillars of advanced graph algorithms — Dijkstra (greedy shortest path), Bellman-Ford (negative weights), Floyd-Warshall (all-pairs), and Union-Find (the most versatile 5-line data structure in competitive programming). Then apply them to Minimum Spanning Trees via Kruskal's and Prim's. These algorithms power routing, networking, scheduling, and clustering — all FAANG-heavy domains.

19.1 Dijkstra's Algorithm — Single-Source Shortest Path

Core Idea

Dijkstra's is a greedy algorithm. At each step, it picks the unvisited vertex with the smallest known distance, finalizes its distance, and relaxes its outgoing edges.

Critical requirement: All edge weights must be non-negative.

Why negative weights break Dijkstra:
  A -- 10 -- B
  |          |
  1         -15
  |          |
  C ------- D

dist[B] finalized as 10 (via A→B).
Later: A→C→D→B has cost 1 + (−15) = −14, which is better.
But B is already finalized! Dijkstra CANNOT go back.
→ Use Bellman-Ford for negative weights.

Implementation with Priority Queue

vector<long long> dijkstra(int start, int n,
                            vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)}
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> minPQ;  // {distance, node}
 
    dist[start] = 0;
    minPQ.push({0, start});
 
    while (!minPQ.empty()) {
        auto [d, u] = minPQ.top(); minPQ.pop();
 
        // Lazy deletion: skip stale entries
        if (d > dist[u]) continue;
 
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                minPQ.push({dist[v], v});
            }
        }
    }
    return dist;
}
// Time:  O((V + E) log V)
// Space: O(V + E)
// dist[v] = shortest distance from start to v (LLONG_MAX if unreachable)

Stale Entry Handling — Critical Detail

// Without lazy deletion, old {large_dist, v} entries stay in the queue.
// When we later pop them, dist[v] may already be finalized as a smaller value.
// The check "if (d > dist[u]) continue" skips these stale entries.
 
// Example:
// Push {10, B} for path A→B
// Find shorter path A→C→B = 5, push {5, B}
// Queue: [{5,B}, {10,B}]
// Pop {5,B}: process B (dist[B]=5 finalized)
// Pop {10,B}: d=10 > dist[B]=5 → SKIP (stale)

Path Reconstruction

vector<long long> dijkstraWithPath(int start, int n,
                                    vector<vector<pair<int,int>>>& adj,
                                    vector<int>& prev) {
    vector<long long> dist(n, LLONG_MAX);
    prev.assign(n, -1);  // prev[v] = node before v on shortest path
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
 
    dist[start] = 0;
    pq.push({0, start});
 
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;            // Record path
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
 
// Reconstruct path from start to end:
vector<int> getPath(vector<int>& prev, int end) {
    vector<int> path;
    for (int v = end; v != -1; v = prev[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

Dijkstra on a Grid

// Minimum cost path on a weighted grid (e.g., LC 1631 Path With Min Effort)
int dijkstraGrid(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>,
                   greater<>> pq;  // {cost, row, col}
 
    dist[0][0] = 0;
    pq.push({0, 0, 0});
 
    while (!pq.empty()) {
        auto [cost, r, c] = pq.top(); pq.pop();
        if (cost > dist[r][c]) continue;
        if (r == R-1 && c == C-1) return cost;
 
        for (int d = 0; d < 4; d++) {
            int nr = r+dx[d], nc = c+dy[d];
            if (nr<0||nr>=R||nc<0||nc>=C) continue;
            int newCost = max(cost, abs(grid[nr][nc]-grid[r][c]));
            if (newCost < dist[nr][nc]) {
                dist[nr][nc] = newCost;
                pq.push({newCost, nr, nc});
            }
        }
    }
    return dist[R-1][C-1];
}

19.2 Bellman-Ford — Negative Weights & Cycle Detection

Core Idea

Works with negative edge weights. Detects negative cycles.

Key insight: After k rounds of relaxing all edges,
dist[v] = shortest path from source to v using at most k edges.
After V-1 rounds: shortest paths (simple paths) are finalized.
If V-th round still updates any distance → negative cycle exists.

vector<long long> bellmanFord(int start, int n,
                               vector<tuple<int,int,int>>& edges) {
    // edges = {u, v, weight} (directed)
    vector<long long> dist(n, LLONG_MAX);
    dist[start] = 0;
 
    // V-1 relaxation rounds
    for (int round = 0; round < n-1; round++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // Early termination: already converged
    }
 
    // Negative cycle detection: V-th round
    for (auto [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            // This edge can still be relaxed → negative cycle!
            return {};  // Signal: negative cycle exists
        }
    }
    return dist;
}
// Time:  O(V × E)
// Space: O(V)

Bellman-Ford with K Relaxations (Cheapest Flights)

// LC 787: Find shortest path from src to dst using at most k+1 edges
vector<int> cheapestFlightsKStops(int n, vector<vector<int>>& flights,
                                   int src, int dst, int k) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
 
    // k+1 edges = k stops in between → k+1 relaxation rounds
    for (int i = 0; i <= k; i++) {
        vector<long long> temp = dist;  // Use previous round's values!
        for (auto& f : flights) {
            int u=f[0], v=f[1], w=f[2];
            if (dist[u] != LLONG_MAX && dist[u]+w < temp[v]) {
                temp[v] = dist[u] + w;
            }
        }
        dist = temp;
    }
    return dist[dst] == LLONG_MAX ? -1 : dist[dst];
}
// Time: O(k × E), Space: O(V)
// Critical: copy dist to temp before each round to prevent using updates
// from the SAME round (would allow more than i edges)

19.3 Floyd-Warshall — All-Pairs Shortest Path

Core Idea

Dynamic programming: dist[i][j] = shortest path from i to j using intermediate vertices from the set {0, 1, ..., k}.

State transition:
dist[i][j] = min(dist[i][j],      ← path not through k
                 dist[i][k] + dist[k][j])  ← path through k

k must be the OUTERMOST loop (process all i,j pairs for each k)

void floydWarshall(int n, vector<vector<long long>>& dist) {
    // dist[i][j] should be initialized to:
    //   0          if i == j
    //   weight     if edge (i,j) exists
    //   LLONG_MAX/2 otherwise (use /2 to avoid overflow in addition)
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    // After: dist[i][j] = shortest path from i to j (or LLONG_MAX/2 if unreachable)
    // Negative cycle: if dist[i][i] < 0 for any i
}
 
// Build the distance matrix from edge list:
vector<vector<long long>> buildFloydMatrix(int n,
                                            vector<tuple<int,int,int>>& edges) {
    const long long INF = 1e18;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto [u, v, w] : edges) {
        dist[u][v] = min(dist[u][v], (long long)w);
        // For undirected: also dist[v][u] = min(dist[v][u], w)
    }
    floydWarshall(n, dist);
    return dist;
}
// Time:  O(V³)
// Space: O(V²)
// Use when: V ≤ ~400 (400³ = 64M ops, feasible)
//           Need all-pairs distances
//           Graph may have negative edges (but no negative cycles)

Floyd-Warshall Applications

// Find the city with fewest reachable neighbors within threshold (LC 1334)
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    vector<vector<long long>> dist(n, vector<long long>(n, 1e9));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto& e : edges) {
        dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];
    }
    for (int k=0;k<n;k++) for (int i=0;i<n;i++) for (int j=0;j<n;j++)
        dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
 
    int ans = -1, minCount = n+1;
    for (int i = n-1; i >= 0; i--) {  // Prefer larger city index on tie
        int count = 0;
        for (int j = 0; j < n; j++)
            if (i != j && dist[i][j] <= distanceThreshold) count++;
        if (count <= minCount) { minCount = count; ans = i; }
    }
    return ans;
}

19.4 Union-Find / Disjoint Set Union (DSU)

DSU maintains a collection of disjoint sets and supports two operations:

find(x): which set does x belong to? (returns the root/representative)
union(x, y): merge the sets containing x and y

Full Implementation with Path Compression & Union by Rank

class DSU {
    vector<int> parent, rank_;
    int components;
 
public:
    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i initially
    }
 
    // Find with PATH COMPRESSION: make every node on the path point to root
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // Recursive path compression
        return parent[x];
    }
 
    // Union by RANK: attach smaller-rank tree under larger-rank tree
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // Already in same set
 
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;             // Attach ry's tree under rx
        if (rank_[rx] == rank_[ry]) rank_[rx]++;  // Only increase if equal
        components--;
        return true;  // Successfully merged
    }
 
    bool connected(int x, int y) { return find(x) == find(y); }
    int  numComponents()          { return components; }
};
// find: O(α(n)) amortized ≈ O(1)    (inverse Ackermann — grows incredibly slowly)
// unite: O(α(n)) amortized ≈ O(1)
// Space: O(n)

Path Compression — Visual

Before find(7):          After find(7):
    1                        1
   / \                    / | \ \
  3   2                  3  2  7  (7 and others now point directly to root 1)
  |   |
  5   4
  |
  7

Without compression: find(7) = O(depth)
With compression:    next find(7) = O(1)

Union by Size (Alternative to Union by Rank)

// More intuitive: always attach smaller set under larger set
class DSU_Size {
    vector<int> parent, size_;
    int components;
public:
    DSU_Size(int n) : parent(n), size_(n, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size_[rx] < size_[ry]) swap(rx, ry);
        parent[ry] = rx;
        size_[rx] += size_[ry];
        components--;
        return true;
    }
    int  getSize(int x)   { return size_[find(x)]; }
    bool connected(int x, int y) { return find(x) == find(y); }
    int  numComponents()  { return components; }
};

DSU Applications

// 1. Cycle detection in undirected graph
bool hasCycleDSU(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) {
        if (!dsu.unite(u, v)) return true;  // Already connected → cycle!
    }
    return false;
}
 
// 2. Count connected components
int countComponents(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) dsu.unite(u, v);
    return dsu.numComponents();
}
 
// 3. Dynamic connectivity (add edges, check connectivity)
DSU dsu(n);
dsu.unite(0, 1);
dsu.unite(2, 3);
dsu.connected(0, 2);  // false — different components
dsu.unite(1, 2);
dsu.connected(0, 3);  // true — now all connected

19.5 Kruskal's Algorithm — MST via Edge Sorting

Core Idea

Sort all edges by weight. Process in ascending order — add an edge to the MST only if it connects two different components (doesn't create a cycle). Stop when n-1 edges are added.

Greedy correctness: Adding the globally cheapest safe edge (one that doesn't
form a cycle) always leads to a minimum spanning tree (Cut Property).

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const { return weight < other.weight; }
};
 
pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());   // Sort by weight ascending
 
    DSU dsu(n);
    long long totalWeight = 0;
    vector<Edge> mstEdges;
 
    for (auto& edge : edges) {
        if (dsu.unite(edge.u, edge.v)) {   // If different components
            mstEdges.push_back(edge);
            totalWeight += edge.weight;
            if ((int)mstEdges.size() == n-1) break;  // MST complete
        }
    }
 
    // If mstEdges.size() < n-1: graph is not connected → no MST
    return {totalWeight, mstEdges};
}
// Time:  O(E log E) for sorting + O(E α(V)) for DSU = O(E log E)
// Space: O(E) for edges + O(V) for DSU

Kruskal's for Minimum Cost to Connect All Points

// LC 1584: Points on a 2D plane, edge weight = Manhattan distance
int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<Edge> edges;
 
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int w = abs(points[i][0]-points[j][0])
                  + abs(points[i][1]-points[j][1]);
            edges.push_back({i, j, w});
        }
 
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long cost = 0;
    int edgeCount = 0;
 
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            cost += e.weight;
            if (++edgeCount == n-1) break;
        }
    }
    return cost;
}
// Time: O(n² log n) — n² edges, sort + DSU

19.6 Prim's Algorithm — MST via Vertex Growing

Core Idea

Start from any vertex. Maintain a priority queue of edges crossing the "tree boundary" (one endpoint in MST, one outside). Always pick the cheapest.

Unlike Kruskal's (global edge view), Prim's grows the MST locally —
like BFS but with a priority queue instead of a regular queue.

long long prims(int start, int n,
                vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight)}
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<>> minPQ;  // {weight, vertex}
 
    minPQ.push({0, start});
    long long totalWeight = 0;
    int edgesAdded = 0;
 
    while (!minPQ.empty() && edgesAdded < n) {
        auto [w, u] = minPQ.top(); minPQ.pop();
        if (inMST[u]) continue;   // Already in MST
 
        inMST[u] = true;
        totalWeight += w;
        edgesAdded++;
 
        for (auto [v, weight] : adj[u]) {
            if (!inMST[v]) {
                minPQ.push({weight, v});
            }
        }
    }
    return totalWeight;
}
// Time:  O((V + E) log V) with binary heap
// Space: O(V + E)

Kruskal's vs. Prim's Comparison

Aspect	Kruskal's	Prim's
Approach	Edge-based (global)	Vertex-based (local)
Key structure	DSU	Priority Queue
Best for	Sparse graphs (E ≈ V)	Dense graphs (E ≈ V²)
Time	O(E log E)	O(E log V)
Handles disconnected	(no MST)	(no MST)
Easier to implement	Slightly	Slightly harder

19.7 Algorithm Decision Guide

SHORTEST PATH PROBLEMS:
│
├── Single source, non-negative weights?
│   └── DIJKSTRA — O((V+E) log V)
│       Use when: road maps, network routing
│
├── Single source, negative weights (no negative cycles)?
│   └── BELLMAN-FORD — O(V×E)
│       Use when: currency exchange rates, arbitrage detection
│
├── Single source, negative weights WITH negative cycle detection?
│   └── BELLMAN-FORD — check if Vth round updates anything
│
├── All pairs, small V (≤ 400)?
│   └── FLOYD-WARSHALL — O(V³)
│       Use when: find all pairwise distances, transitive closure
│
├── Single source, limited number of edges (k stops)?
│   └── BELLMAN-FORD (k rounds) — O(k × E)
│
└── Unweighted graph (all edges weight 1)?
    └── BFS — O(V+E) — always prefer over Dijkstra for unweighted

CONNECTIVITY PROBLEMS:
│
├── Dynamic: add edges, check connectivity?
│   └── DSU — O(α(n)) per operation
│
├── Count connected components?
│   └── DSU or DFS/BFS — O(V+E)
│
└── Detect cycle in undirected graph?
    └── DSU — O(E α(V))

MINIMUM SPANNING TREE:
│
├── Sparse graph (E ≈ V)?
│   └── KRUSKAL'S — O(E log E)
│
└── Dense graph (E ≈ V²)?
    └── PRIM'S — O(E log V) with binary heap, O(V²) with adjacency matrix

Complexity Summary

Algorithm	Time	Space	Negative Weights	Negative Cycles
Dijkstra	O((V+E) log V)	O(V+E)	No	No
Bellman-Ford	O(V×E)	O(V)	Yes	Detects
Floyd-Warshall	O(V³)	O(V²)	Yes	Detects (dist[i][i]<0)
BFS (unweighted)	O(V+E)	O(V)	N/A	N/A
DSU (find/union)	O(α(n))	O(V)	N/A	N/A
Kruskal's	O(E log E)	O(V+E)	(MST)	N/A
Prim's	O((V+E) log V)	O(V+E)	(MST)	N/A

19.8 Sample Problems

Problem 1 — Network Delay Time (Medium) — LC 743

Find the time for all nodes to receive a signal from source k. Return -1 if not possible.

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int,int>>> adj(n+1);
    for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
 
    vector<long long> dist(n+1, LLONG_MAX);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    dist[k] = 0; pq.push({0, k});
 
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u]+w < dist[v]) {
                dist[v] = dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    }
    long long ans = *max_element(dist.begin()+1, dist.end());
    return ans == LLONG_MAX ? -1 : ans;
}
// Time: O((V+E) log V), Space: O(V+E)

Problem 2 — Cheapest Flights Within K Stops (Medium) — LC 787

int findCheapestPrice(int n, vector<vector<int>>& flights,
                      int src, int dst, int k) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
 
    for (int i = 0; i <= k; i++) {
        vector<long long> temp = dist;
        for (auto& f : flights) {
            int u=f[0], v=f[1], w=f[2];
            if (dist[u]!=LLONG_MAX && dist[u]+w < temp[v])
                temp[v] = dist[u]+w;
        }
        dist = temp;
    }
    return dist[dst]==LLONG_MAX ? -1 : (int)dist[dst];
}
// Time: O(k × E), Space: O(V)
// Bellman-Ford with exactly k+1 rounds (k stops = k+1 edges)

Problem 3 — Path With Minimum Effort (Medium) — LC 1631

Find a path from top-left to bottom-right minimizing the maximum absolute difference between consecutive cells.

int minimumEffortPath(vector<vector<int>>& heights) {
    int R=heights.size(), C=heights[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>,
                   greater<>> pq;
    dist[0][0]=0; pq.push({0,0,0});
 
    while (!pq.empty()) {
        auto [effort,r,c] = pq.top(); pq.pop();
        if (effort > dist[r][c]) continue;
        if (r==R-1&&c==C-1) return effort;
        for (int d=0;d<4;d++) {
            int nr=r+dx[d], nc=c+dy[d];
            if (nr<0||nr>=R||nc<0||nc>=C) continue;
            int newEffort = max(effort, abs(heights[nr][nc]-heights[r][c]));
            if (newEffort < dist[nr][nc]) {
                dist[nr][nc]=newEffort;
                pq.push({newEffort,nr,nc});
            }
        }
    }
    return 0;
}
// Time: O(R×C×log(R×C)), Space: O(R×C)

Problem 4 — Path With Maximum Probability (Medium) — LC 1514

Find the path with maximum probability of success from start to end.

double maxProbability(int n, vector<vector<int>>& edges,
                      vector<double>& succProb, int start, int end) {
    vector<vector<pair<int,double>>> adj(n);
    for (int i=0;i<(int)edges.size();i++) {
        adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
        adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
    }
 
    vector<double> prob(n, 0.0);
    priority_queue<pair<double,int>> maxPQ;  // Max probability on top
    prob[start] = 1.0;
    maxPQ.push({1.0, start});
 
    while (!maxPQ.empty()) {
        auto [p, u] = maxPQ.top(); maxPQ.pop();
        if (p < prob[u]) continue;
        if (u == end) return p;
        for (auto [v, w] : adj[u]) {
            if (prob[u]*w > prob[v]) {
                prob[v] = prob[u]*w;
                maxPQ.push({prob[v], v});
            }
        }
    }
    return 0.0;
}
// Dijkstra variant: max probability instead of min distance
// Time: O((V+E) log V), Space: O(V+E)

Problem 5 — Find the City With Smallest Number of Neighbors (Medium) — LC 1334

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    vector<vector<long long>> dist(n, vector<long long>(n, 1e9));
    for (int i=0;i<n;i++) dist[i][i]=0;
    for (auto& e:edges) {
        dist[e[0]][e[1]]=dist[e[1]][e[0]]=e[2];
    }
    for (int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
 
    int ans=-1, minCnt=n+1;
    for (int i=n-1;i>=0;i--) {  // Largest index breaks ties
        int cnt=0;
        for (int j=0;j<n;j++) if(i!=j&&dist[i][j]<=distanceThreshold) cnt++;
        if (cnt<=minCnt) { minCnt=cnt; ans=i; }
    }
    return ans;
}
// Time: O(n³) Floyd-Warshall + O(n²) scan, Space: O(n²)

Problem 6 — Number of Connected Components (Medium) — LC 323

int countComponents(int n, vector<vector<int>>& edges) {
    DSU dsu(n);
    for (auto& e : edges) dsu.unite(e[0], e[1]);
    return dsu.numComponents();
}
// Time: O(E α(V)), Space: O(V)

Problem 7 — Redundant Connection (Medium) — LC 684

Find the edge that creates a cycle — removing it makes the graph a tree.

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    DSU dsu(n+1);  // 1-indexed
    for (auto& e : edges) {
        if (!dsu.unite(e[0], e[1])) return e;  // Already connected → redundant!
    }
    return {};
}
// Time: O(E α(V)), Space: O(V)

Problem 8 — Accounts Merge (Medium) — LC 721

Merge accounts that share at least one email address.

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, int> emailToIdx;
    DSU dsu(accounts.size());
 
    for (int i = 0; i < (int)accounts.size(); i++) {
        for (int j = 1; j < (int)accounts[i].size(); j++) {
            const string& email = accounts[i][j];
            if (emailToIdx.count(email)) {
                dsu.unite(i, emailToIdx[email]);  // Same email → same account
            } else {
                emailToIdx[email] = i;
            }
        }
    }
 
    // Group emails by their root account
    unordered_map<int, set<string>> groups;
    for (auto& [email, idx] : emailToIdx)
        groups[dsu.find(idx)].insert(email);
 
    vector<vector<string>> result;
    for (auto& [root, emails] : groups) {
        vector<string> merged = {accounts[root][0]};  // Name
        merged.insert(merged.end(), emails.begin(), emails.end());
        result.push_back(merged);
    }
    return result;
}
// Time: O(N×K×α(N×K)) where N=accounts, K=max emails per account

Problem 9 — Min Cost to Connect All Points (Medium) — LC 1584

int minCostConnectPoints(vector<vector<int>>& pts) {
    int n=pts.size();
    // Prim's: O(n² log n) — better than Kruskal's O(n² log n²) for dense graphs
    vector<int> minDist(n, INT_MAX);
    vector<bool> inMST(n, false);
    minDist[0] = 0;
    long long cost = 0;
 
    for (int iter = 0; iter < n; iter++) {
        // Find nearest non-MST node
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!inMST[i] && (u==-1 || minDist[i]<minDist[u])) u=i;
 
        inMST[u] = true;
        cost += minDist[u];
 
        // Update distances to remaining nodes
        for (int v = 0; v < n; v++) {
            if (!inMST[v]) {
                int d = abs(pts[u][0]-pts[v][0]) + abs(pts[u][1]-pts[v][1]);
                minDist[v] = min(minDist[v], d);
            }
        }
    }
    return cost;
}
// Time: O(n²) — dense graph, adjacency matrix Prim's
// Kruskal's would be O(n² log n) due to sorting all n² edges

Problem 10 — Swim in Rising Water (Hard) — LC 778

You can swim when water level ≥ cell value. Find minimum time to reach bottom-right.

int swimInWater(vector<vector<int>>& grid) {
    int n=grid.size();
    // Dijkstra: cost of path = maximum grid value along path
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>, greater<>> pq;
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    dist[0][0]=grid[0][0]; pq.push({grid[0][0],0,0});
 
    while (!pq.empty()) {
        auto [t,r,c]=pq.top();pq.pop();
        if (t>dist[r][c]) continue;
        if (r==n-1&&c==n-1) return t;
        for (int d=0;d<4;d++) {
            int nr=r+dx[d],nc=c+dy[d];
            if (nr<0||nr>=n||nc<0||nc>=n) continue;
            int nt=max(t,grid[nr][nc]);
            if (nt<dist[nr][nc]){dist[nr][nc]=nt;pq.push({nt,nr,nc});}
        }
    }
    return dist[n-1][n-1];
}
// Time: O(n² log n), Space: O(n²)

Problem 11 — Evaluate Division (Medium) — LC 399

Given equations a/b = k, find values of other divisions.

// Model as weighted graph: a → b with weight k, b → a with weight 1/k
// Query c/d = shortest multiplicative path from c to d
vector<double> calcEquation(vector<vector<string>>& equations,
                             vector<double>& values,
                             vector<vector<string>>& queries) {
    unordered_map<string, vector<pair<string,double>>> adj;
 
    for (int i = 0; i < (int)equations.size(); i++) {
        auto& a = equations[i][0], &b = equations[i][1];
        adj[a].push_back({b, values[i]});
        adj[b].push_back({a, 1.0/values[i]});
    }
 
    auto bfs = [&](const string& src, const string& dst) -> double {
        if (!adj.count(src)||!adj.count(dst)) return -1.0;
        if (src==dst) return 1.0;
        unordered_map<string,double> visited;
        queue<pair<string,double>> q;
        q.push({src, 1.0});
        visited[src] = 1.0;
        while (!q.empty()) {
            auto [u, prod] = q.front(); q.pop();
            for (auto [v, w] : adj[u]) {
                if (!visited.count(v)) {
                    double newProd = prod * w;
                    if (v == dst) return newProd;
                    visited[v] = newProd;
                    q.push({v, newProd});
                }
            }
        }
        return -1.0;
    };
 
    vector<double> result;
    for (auto& q : queries) result.push_back(bfs(q[0], q[1]));
    return result;
}
// Time: O((E + Q) × V), Space: O(V + E)

Problem 12 — Checking Existence of Edge Length Limited Paths (Hard) — LC 1697

For each query (u, v, limit): does there exist a path from u to v where ALL edge weights are strictly less than limit?

// Offline approach: sort queries and edges by limit/weight
// Process in order, adding edges that are < current limit, check connectivity
vector<bool> distanceLimitedPathsExist(int n,
    vector<vector<int>>& edgeList,
    vector<vector<int>>& queries) {
 
    // Sort edges by weight
    sort(edgeList.begin(), edgeList.end(),
         [](auto& a, auto& b){ return a[2] < b[2]; });
 
    // Sort queries by limit, keep original index
    int q = queries.size();
    vector<int> qIdx(q);
    iota(qIdx.begin(), qIdx.end(), 0);
    sort(qIdx.begin(), qIdx.end(),
         [&](int a, int b){ return queries[a][2] < queries[b][2]; });
 
    DSU dsu(n);
    int ei = 0;
    vector<bool> result(q);
 
    for (int qi : qIdx) {
        int u=queries[qi][0], v=queries[qi][1], limit=queries[qi][2];
 
        // Add all edges with weight < limit
        while (ei < (int)edgeList.size() && edgeList[ei][2] < limit) {
            dsu.unite(edgeList[ei][0], edgeList[ei][1]);
            ei++;
        }
 
        result[qi] = dsu.connected(u, v);
    }
    return result;
}
// Time: O((E + Q) log(E + Q)), Space: O(V + Q)

19.9 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Network Delay Time	Medium	Dijkstra's single-source	LC 743
2	Cheapest Flights Within K Stops	Medium	Bellman-Ford (k rounds)	LC 787
3	Path With Minimum Effort	Medium	Dijkstra on grid (max cost)	LC 1631
4	Redundant Connection	Medium	DSU cycle detection	LC 684
5	Accounts Merge	Medium	DSU grouping by shared element	LC 721
6	Min Cost to Connect All Points	Medium	Prim's MST (dense graph)	LC 1584
7	Swim in Rising Water	Hard	Dijkstra (min of max along path)	LC 778
8	Edge Length Limited Paths	Hard	Offline DSU + sorted queries	LC 1697

Suggested order: #1 (Network Delay) — Dijkstra template. #2 (Cheapest Flights) — Bellman-Ford with k constraint. #3 (Min Effort) — Dijkstra on grid. #4 (Redundant Connection) — DSU in 3 lines. #5 (Accounts Merge) — DSU for grouping. #6 (Connect Points) — Prim's dense MST. #7 and #8 are hard applications — Swim in Water (min-max Dijkstra) and Edge Limited Paths (offline DSU) are both interview classics.