Graph Algorithms (C++) — Step-by-Step with Full Code

Scope: Core graph algorithms with clear steps, complete C++ implementations, worked examples, and time/space
complexities. No fluff.

Contents: Representation • DFS • BFS • Topological Sort (Kahn + DFS) • Cycle Detection (Undirected/Directed) •
Bipartite Check • Shortest Path on DAG • Dijkstra • 0-1 BFS • Bellman-Ford • Floyd–Warshall • Minimum Spanning
Trees (Kruskal + Prim) • Disjoint Set Union • Strongly Connected Components (Kosaraju) • Bridges & Articulation
Points • Multi-source BFS • Grid BFS. Plus 20 LeetCode-style practice problems with solutions.

1) Graph Representation
Use adjacency list for sparse graphs and adjacency matrix for dense graphs. We default to adjacency list in most code.
Adjacency List Template (0-indexed)
#include <bits/stdc++.h>
using namespace std;

struct Graph {
int n;
vector<vector<pair<int,int>>> adj; // for weighted graphs: (to, weight)
vector<vector<int>> adj_unw; // for unweighted graphs

Graph(int n): n(n), adj(n), adj_unw(n) {}

void add_edge_unw(int u, int v, bool undirected=true) {

adj_unw[u].push_back(v);
if (undirected) adj_unw[v].push_back(u);
}

void add_edge_w(int u, int v, int w, bool undirected=false) {

adj[u].push_back({v,w});
if (undirected) adj[v].push_back({u,w});
}
};
int main(){ return 0; }
Complexity: Building adjacency list O(N + M). Space: O(N + M).
2) Depth-First Search (DFS)
Steps: (1) Choose a start node, (2) mark visited, (3) recurse/iterate to unvisited neighbors, (4) postorder actions if
needed.
#include <bits/stdc++.h>
using namespace std;

void dfs_rec(int u, const vector<vector<int>>& g, vector<int>& vis) {

vis[u] = 1;
// process node u here if needed
for (int v: g[u]) if (!vis[v]) dfs_rec(v, g, vis);
}

vector<int> dfs_order_iter(int s, const vector<vector<int>>& g) {

vector<int> vis(g.size()), order;
stack<int> st; st.push(s);
while(!st.empty()){
int u = st.top(); st.pop();
if (vis[u]) continue;
vis[u]=1;
order.push_back(u);
// push neighbors (optionally reverse for specific order)
for (int v: g[u]) if(!vis[v]) st.push(v);
}
return order;
}

int main(){ return 0; }

Time: O(N + M), Space: O(N) recursion stack (or O(N) for iterative).
3) Breadth-First Search (BFS)
Steps: (1) Push start into queue, (2) pop and visit, (3) push unvisited neighbors; gives shortest edges count on
unweighted graphs.
#include <bits/stdc++.h>
using namespace std;

vector<int> bfs_dist(int s, const vector<vector<int>>& g) {

const int INF = 1e9;
vector<int> dist(g.size(), INF);
queue<int> q;
dist[s] = 0; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for (int v: g[u]) if (dist[v]==INF){
dist[v] = dist[u] + 1;
q.push(v);
}
}
return dist;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N).
4) Topological Sort
Kahn's Algorithm (BFS on indegrees)
#include <bits/stdc++.h>
using namespace std;

vector<int> topo_kahn(int n, const vector<vector<int>>& g){

vector<int> indeg(n);
for(int u=0;u<n;++u) for(int v: g[u]) indeg[v]++;
queue<int> q;
for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i);
vector<int> order;
while(!q.empty()){
int u=q.front(); q.pop();
order.push_back(u);
for(int v: g[u]){
if(--indeg[v]==0) q.push(v);
}
}
return order; // if size < n, there's a cycle
}
int main(){ return 0; }
DFS Postorder (reverse finishing times)
#include <bits/stdc++.h>
using namespace std;

void dfs(int u, const vector<vector<int>>& g, vector<int>& vis, vector<int>& order){

vis[u]=1;
for(int v: g[u]) if(!vis[v]) dfs(v,g,vis,order);
order.push_back(u);
}
vector<int> topo_dfs(int n, const vector<vector<int>>& g){
vector<int> vis(n), order;
for(int i=0;i<n;++i) if(!vis[i]) dfs(i,g,vis,order);
reverse(order.begin(), order.end());
return order;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N). DAG only.
5) Cycle Detection
Undirected (DFS with parent)
#include <bits/stdc++.h>
using namespace std;

bool dfs_cycle_und(int u, int p, const vector<vector<int>>& g, vector<int>& vis){

vis[u]=1;
for(int v: g[u]){
 if(v==p) continue;
if(vis[v]) return true;
if(dfs_cycle_und(v,u,g,vis)) return true;
}
return false;
}
bool has_cycle_undirected(int n, const vector<vector<int>>& g){
vector<int> vis(n);
for(int i=0;i<n;++i) if(!vis[i]) if(dfs_cycle_und(i,-1,g,vis)) return true;
return false;
}
int main(){ return 0; }
Directed (coloring: 0=unseen,1=stack,2=done)
#include <bits/stdc++.h>
using namespace std;

bool dfs_cycle_dir(int u, const vector<vector<int>>& g, vector<int>& col){

col[u]=1;
for(int v: g[u]){
if(col[v]==1) return true;
if(col[v]==0 && dfs_cycle_dir(v,g,col)) return true;
}
col[u]=2;
return false;
}
bool has_cycle_directed(int n, const vector<vector<int>>& g){
vector<int> col(n,0);
for(int i=0;i<n;++i) if(col[i]==0) if(dfs_cycle_dir(i,g,col)) return true;
return false;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N).
6) Bipartite Check (BFS coloring)
#include <bits/stdc++.h>
using namespace std;

bool is_bipartite(int n, const vector<vector<int>>& g){

vector<int> color(n, -1);
queue<int> q;
for(int i=0;i<n;++i) if(color[i]==-1){
color[i]=0; q.push(i);
while(!q.empty()){
int u=q.front(); q.pop();
for(int v: g[u]){
if(color[v]==-1){
color[v]=color[u]^1; q.push(v);
}else if(color[v]==color[u]) return false;
}
}
}
return true;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N).
7) Shortest Path on DAG (weights allowed)
#include <bits/stdc++.h>
using namespace std;

void topo_dfs(int u, const vector<vector<pair<int,int>>>& g, vector<int>& vis, vector<int>& order){

vis[u]=1;
for(auto [v,w]: g[u]) if(!vis[v]) topo_dfs(v,g,vis,order);
order.push_back(u);
}
vector<long long> dag_shortest_paths(int n, const vector<vector<pair<int,int>>>& g, int s){
vector<int> vis(n), order;
for(int i=0;i<n;++i) if(!vis[i]) topo_dfs(i,g,vis,order);
reverse(order.begin(), order.end());
const long long INF = (1LL<<60);
vector<long long> dist(n, INF);
dist[s]=0;
 for(int u: order){
if(dist[u]==INF) continue;
for(auto [v,w]: g[u]) dist[v] = min(dist[v], dist[u]+w);
}
return dist;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N). DAG only.
8) Dijkstra (non-negative weights)
#include <bits/stdc++.h>
using namespace std;

vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& g, int s){

const long long INF = (1LL<<60);
vector<long long> dist(n, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
dist[s]=0; pq.push({0,s});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(d!=dist[u]) continue;
for(auto [v,w]: g[u]){
if(dist[v] > d + w){
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main(){ return 0; }
Time: O((N + M) log N) with binary heap; Space: O(N).
9) 0-1 BFS (edge weights are 0 or 1)
#include <bits/stdc++.h>
using namespace std;

vector<int> zero_one_bfs(int n, const vector<vector<pair<int,int>>>& g, int s){

const int INF = 1e9;
deque<int> dq;
vector<int> dist(n, INF);
dist[s]=0; dq.push_front(s);
while(!dq.empty()){
int u = dq.front(); dq.pop_front();
for(auto [v,w]: g[u]){
int nd = dist[u] + w;
if(nd < dist[v]){
dist[v] = nd;
if(w==0) dq.push_front(v);
else dq.push_back(v);
}
}
}
return dist;
}
int main(){ return 0; }
Time: O(N + M), Space: O(N).
10) Bellman–Ford (handles negative weights, detects negative
cycles)
#include <bits/stdc++.h>
using namespace std;

struct Edge{ int u,v; long long w; };

pair<vector<long long>, bool> bellman_ford(int n, const vector<Edge>& edges, int s){

const long long INF = (1LL<<60);
vector<long long> dist(n, INF);
dist[s]=0;
for(int i=0;i<n-1;++i){
bool any=false;
 for(auto &e: edges){
if(dist[e.u]==INF) continue;
if(dist[e.v] > dist[e.u] + e.w){
dist[e.v] = dist[e.u] + e.w;
any=true;
}
}
if(!any) break;
}
bool neg_cycle=false;
for(auto &e: edges){
if(dist[e.u]!=INF && dist[e.v] > dist[e.u] + e.w){
neg_cycle=true; break;
}
}
return {dist, neg_cycle};
}
int main(){ return 0; }
Time: O(N*M), Space: O(N).
11) Floyd–Warshall (all-pairs shortest paths)
#include <bits/stdc++.h>
using namespace std;

vector<vector<long long>> floyd_warshall(int n, vector<vector<long long>> dist){

const long long INF = (1LL<<60);
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]<INF && dist[k][j]<INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
return dist;
}
int main(){ return 0; }
Time: O(N^3), Space: O(N^2).
12) Disjoint Set Union (Union-Find)
#include <bits/stdc++.h>
using namespace std;

struct DSU {
int n;
vector<int> p, r;
DSU(int n): n(n), p(n), r(n,0){ iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
bool unite(int a, int b){
a=find(a); b=find(b);
if(a==b) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
return true;
}
};
int main(){ return 0; }
Ops nearly amortized α(N). Space: O(N).
13) Minimum Spanning Tree — Kruskal
#include <bits/stdc++.h>
using namespace std;

struct Edge{ int u,v; int w; };

long long mst_kruskal(int n, vector<Edge>& edges){
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.w<b.w; });
vector<int> p(n), r(n,0); iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x){ return p[x]==x ? x : p[x]=find(p[x]); };
auto unite = [&](int a, int b){
a=find(a); b=find(b);
if(a==b) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a; if(r[a]==r[b]) r[a]++;
return true;
 };
long long cost=0; int used=0;
for(auto &e: edges){
if(unite(e.u,e.v)){
cost += e.w;
if(++used==n-1) break;
}
}
return (used==n-1 ? cost : (long long)-1);
}
int main(){ return 0; }
Time: O(M log M) for sorting; unions near O(M α(N)). Space: O(N).
14) Minimum Spanning Tree — Prim (binary heap)
#include <bits/stdc++.h>
using namespace std;

long long mst_prim(int n, const vector<vector<pair<int,int>>>& g){

vector<char> vis(n,0);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // (w, v)
pq.push({0,0});
long long cost=0; int picked=0;
while(!pq.empty()){
auto [w,u]=pq.top(); pq.pop();
if(vis[u]) continue;
vis[u]=1; cost += w; picked++;
for(auto [v,wt]: g[u]) if(!vis[v]) pq.push({wt,v});
}
return (picked==n ? cost : (long long)-1);
}
int main(){ return 0; }
Time: O(M log N). Space: O(N).
15) Strongly Connected Components — Kosaraju
#include <bits/stdc++.h>
using namespace std;

void dfs1(int u, const vector<vector<int>>& g, vector<int>& vis, vector<int>& order){

vis[u]=1;
for(int v: g[u]) if(!vis[v]) dfs1(v,g,vis,order);
order.push_back(u);
}
void dfs2(int u, const vector<vector<int>>& rg, vector<int>& comp, int cid){
comp[u]=cid;
for(int v: rg[u]) if(comp[v]==-1) dfs2(v,rg,comp,cid);
}
int kosaraju(int n, const vector<vector<int>>& g, vector<int>& comp){
vector<vector<int>> rg(n);
for(int u=0;u<n;++u) for(int v: g[u]) rg[v].push_back(u);
vector<int> vis(n,0), order; order.reserve(n);
for(int i=0;i<n;++i) if(!vis[i]) dfs1(i,g,vis,order);
reverse(order.begin(), order.end());
comp.assign(n,-1);
int cid=0;
for(int u: order) if(comp[u]==-1) dfs2(u,rg,comp,cid++);
return cid; // number of components
}
int main(){ return 0; }
Time: O(N + M), Space: O(N + M).
16) Bridges & Articulation Points (Tarjan-time)
#include <bits/stdc++.h>
using namespace std;

struct Tarjan {
int n, timer=0;
vector<vector<int>> g;
vector<int> tin, low, is_art;
vector<pair<int,int>> bridges;
Tarjan(int n): n(n), g(n), tin(n,-1), low(n,-1), is_art(n,0) {}
void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
void dfs(int u, int p=-1){
 tin[u]=low[u]=timer++;
int children=0;
for(int v: g[u]){
if(v==p) continue;
if(tin[v]!=-1){
low[u]=min(low[u], tin[v]);
} else {
dfs(v,u);
low[u]=min(low[u], low[v]);
if(low[v] > tin[u]) bridges.push_back({u,v});
if(p!=-1 && low[v] >= tin[u]) is_art[u]=1;
children++;
}
}
if(p==-1 && children>1) is_art[u]=1;
}
};
int main(){ return 0; }
Time: O(N + M), Space: O(N).
17) Multi-source BFS & Grid BFS
Multi-source BFS
#include <bits/stdc++.h>
using namespace std;

vector<int> multi_source_bfs(int n, const vector<vector<int>>& g, const vector<int>& sources){

const int INF = 1e9;
vector<int> dist(n, INF);
queue<int> q;
for(int s: sources){ dist[s]=0; q.push(s); }
while(!q.empty()){
int u=q.front(); q.pop();
for(int v: g[u]) if(dist[v]==INF){
dist[v]=dist[u]+1; q.push(v);
}
}
return dist;
}
int main(){ return 0; }
Grid BFS (4-dir)
#include <bits/stdc++.h>
using namespace std;

int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

int grid_bfs(vector<string>& grid, pair<int,int> s, pair<int,int> t){
int n=grid.size(), m=grid[0].size();
const int INF=1e9;
vector<vector<int>> dist(n, vector<int>(m, INF));
queue<pair<int,int>> q;
dist[s.first][s.second]=0; q.push(s);
while(!q.empty()){
auto [x,y]=q.front(); q.pop();
if(make_pair(x,y)==t) return dist[x][y];
for(int k=0;k<4;++k){
int nx=x+dx[k], ny=y+dy[k];
if(nx<0||ny<0||nx>=n||ny>=m) continue;
if(grid[nx][ny]=='#') continue; // wall
if(dist[nx][ny]==INF){
dist[nx][ny]=dist[x][y]+1;
q.push({nx,ny});
}
}
}
return -1;
}
int main(){ return 0; }
Time: O(N*M) for grid of N×M. Space: O(N*M).
Practice: 20 LeetCode-Style Problems (with C++ Solutions)
P1. Number of Connected Components (Undirected)
Given n nodes (0..n-1) and edges, return the number of connected components.
#include <bits/stdc++.h>
using namespace std;
int countComponents(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
vector<int> vis(n,0); int comps=0;
function<void(int)> dfs=[&](int u){
vis[u]=1;
for(int v: g[u]) if(!vis[v]) dfs(v);
};
for(int i=0;i<n;++i) if(!vis[i]){ comps++; dfs(i); }
return comps;
}

P2. Shortest Path in Unweighted Graph

Given n and edges and source s, compute shortest distance to all nodes.
#include <bits/stdc++.h>
using namespace std;
vector<int> shortestPathUnw(int n, vector<vector<int>>& edges, int s){
vector<vector<int>> g(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
const int INF=1e9;
vector<int> dist(n, INF); queue<int> q; dist[s]=0; q.push(s);
while(!q.empty()){
int u=q.front(); q.pop();
for(int v: g[u]) if(dist[v]==INF){ dist[v]=dist[u]+1; q.push(v); }
}
return dist;
}

P3. Detect Cycle in Undirected Graph

Return true if an undirected graph has a cycle.
#include <bits/stdc++.h>
using namespace std;
bool dfs(int u,int p,vector<vector<int>>& g,vector<int>& vis){
vis[u]=1;
for(int v: g[u]){
if(v==p) continue;
if(vis[v]) return true;
if(dfs(v,u,g,vis)) return true;
}
return false;
}
bool hasCycle(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n); for(auto &e: edges){ g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
vector<int> vis(n);
for(int i=0;i<n;++i) if(!vis[i] && dfs(i,-1,g,vis)) return true;
return false;
}

P4. Detect Cycle in Directed Graph

Return true if a directed graph has a cycle.
#include <bits/stdc++.h>
using namespace std;
bool dfs(int u, vector<vector<int>>& g, vector<int>& col){
col[u]=1;
for(int v: g[u]){
if(col[v]==1) return true;
if(col[v]==0 && dfs(v,g,col)) return true;
}
col[u]=2; return false;
}
bool hasCycleDirected(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n); for(auto &e: edges) g[e[0]].push_back(e[1]);
vector<int> col(n,0);
for(int i=0;i<n;++i) if(col[i]==0 && dfs(i,g,col)) return true;
return false;
}

P5. Topological Sort (Return Any)

Given a DAG, return a topological ordering.
#include <bits/stdc++.h>
using namespace std;
vector<int> topoSort(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n); vector<int> indeg(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); indeg[e[1]]++; }
queue<int> q; for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i);
vector<int> order;
while(!q.empty()){
int u=q.front(); q.pop();
order.push_back(u);
for(int v: g[u]) if(--indeg[v]==0) q.push(v);
}
if((int)order.size()!=n) return {}; // cycle
return order;
}

P6. Course Schedule (Feasible?)

Given prerequisites, determine if all courses can be finished (no directed cycle).
#include <bits/stdc++.h>
using namespace std;
bool canFinish(int n, vector<vector<int>>& pre){
vector<vector<int>> g(n); vector<int> indeg(n);
for(auto &p: pre){ g[p[1]].push_back(p[0]); indeg[p[0]]++; }
queue<int> q; for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i);
int taken=0;
while(!q.empty()){
int u=q.front(); q.pop(); taken++;
for(int v: g[u]) if(--indeg[v]==0) q.push(v);
}
return taken==n;
}

P7. Number of Islands (Grid BFS)

Count connected components of '1' in a grid of '0'/'1' (4-dir).
#include <bits/stdc++.h>
using namespace std;
int numIslands(vector<vector<char>>& grid){
int n=grid.size(); if(!n) return 0; int m=grid[0].size();
vector<vector<int>> vis(n, vector<int>(m,0));
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
auto bfs=[&](int sx,int sy){
queue<pair<int,int>> q; q.push({sx,sy}); vis[sx][sy]=1;
while(!q.empty()){
auto [x,y]=q.front(); q.pop();
for(int k=0;k<4;++k){
int nx=x+dx[k], ny=y+dy[k];
if(nx<0||ny<0||nx>=n||ny>=m) continue;
if(!vis[nx][ny] && grid[nx][ny]=='1'){
vis[nx][ny]=1; q.push({nx,ny});
}
}
}
};
int cnt=0;
for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(grid[i][j]=='1' && !vis[i][j]){ cnt++; bfs(i,j); }
return cnt;
}

P8. Rotting Oranges (Multi-source BFS)

Return minutes until all oranges rot, or -1 if impossible.
#include <bits/stdc++.h>
using namespace std;
int orangesRotting(vector<vector<int>>& grid){
int n=grid.size(), m=grid[0].size();
queue<pair<int,int>> q; int fresh=0;
for(int i=0;i<n;++i) for(int j=0;j<m;++j){
if(grid[i][j]==2) q.push({i,j});
else if(grid[i][j]==1) fresh++;
}
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1}, minutes=0;
while(!q.empty() && fresh){
int sz=q.size(); minutes++;
while(sz--){
auto [x,y]=q.front(); q.pop();
for(int k=0;k<4;++k){
int nx=x+dx[k], ny=y+dy[k];
if(nx<0||ny<0||nx>=n||ny>=m) continue;
 if(grid[nx][ny]==1){
grid[nx][ny]=2; fresh--; q.push({nx,ny});
}
}
}
}
return fresh? -1 : minutes;
}

P9. Clone Graph

Clone an undirected graph given a node pointer.
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int val; vector<Node*> neighbors;
Node(): val(0) {}
Node(int _val): val(_val) {}
};
Node* cloneGraph(Node* node){
if(!node) return nullptr;
unordered_map<Node*, Node*> mp;
queue<Node*> q; q.push(node);
mp[node] = new Node(node->val);
while(!q.empty()){
Node* u=q.front(); q.pop();
for(Node* w: u->neighbors){
if(!mp.count(w)){
mp[w]=new Node(w->val);
q.push(w);
}
mp[u]->neighbors.push_back(mp[w]);
}
}
return mp[node];
}

P10. Evaluate Division (Graph + DFS/BFS)

Given equations a/b = k, answer division queries.
#include <bits/stdc++.h>
using namespace std;
vector<double> calcEquation(vector<vector<string>>& eq, vector<double>& val, vector<vector<string>>& q){
unordered_map<string, vector<pair<string,double>>> g;
for(int i=0;i<(int)eq.size();++i){
auto &e=eq[i]; double k=val[i];
g[e[0]].push_back({e[1], k});
g[e[1]].push_back({e[0], 1.0/k});
}
vector<double> ans;
for(auto &qq: q){
string s=qq[0], t=qq[1];
if(!g.count(s) || !g.count(t)){ ans.push_back(-1.0); continue; }
unordered_map<string,double> dist; queue<string> qu;
dist[s]=1.0; qu.push(s);
double res=-1.0;
while(!qu.empty()){
string u=qu.front(); qu.pop();
if(u==t){ res=dist[u]; break; }
for(auto &pr: g[u]){
if(!dist.count(pr.first)){
dist[pr.first]=dist[u]*pr.second;
qu.push(pr.first);
}
}
}
ans.push_back(res);
}
return ans;
}

P11. Reconstruct Itinerary (Hierholzer variant)

Find lexicographically smallest itinerary starting from JFK using all tickets once.
#include <bits/stdc++.h>
using namespace std;
vector<string> findItinerary(vector<vector<string>>& tickets){
unordered_map<string, multiset<string>> g;
for(auto &t: tickets) g[t[0]].insert(t[1]);
vector<string> route; stack<string> st; st.push("JFK");
 while(!st.empty()){
string u=st.top();
if(g[u].empty()){ route.push_back(u); st.pop(); }
else{
auto it=g[u].begin();
string v=*it; g[u].erase(it);
st.push(v);
}
}
reverse(route.begin(), route.end());
return route;
}

P12. Cheapest Flights Within K Stops (Bellman-Ford layers)

Find cheapest price from src to dst with at most K stops.
#include <bits/stdc++.h>
using namespace std;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K){
const int INF=1e9;
vector<int> dist(n, INF); dist[src]=0;
for(int i=0;i<=K;++i){
vector<int> ndist=dist;
for(auto &f: flights){
int u=f[0], v=f[1], w=f[2];
if(dist[u]==INF) continue;
ndist[v]=min(ndist[v], dist[u]+w);
}
dist.swap(ndist);
}
return dist[dst]==INF? -1: dist[dst];
}

P13. Network Delay Time (Dijkstra)

Given times u->v with weight w, find time for all nodes to receive signal from k.
#include <bits/stdc++.h>
using namespace std;
int networkDelayTime(vector<vector<int>>& times, int n, int k){
vector<vector<pair<int,int>>> g(n+1);
for(auto &t: times) g[t[0]].push_back({t[1], t[2]});
const int INF=1e9;
vector<int> dist(n+1, INF); dist[k]=0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,k});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(d!=dist[u]) continue;
for(auto [v,w]: g[u]) if(dist[v] > d + w){
dist[v]=d+w; pq.push({dist[v], v});
}
}
int ans=0;
for(int i=1;i<=n;++i) ans=max(ans, dist[i]);
return ans>=INF? -1: ans;
}

P14. Minimum Spanning Tree Cost (Kruskal)

Return MST total weight or -1 if graph disconnected.
#include <bits/stdc++.h>
using namespace std;
struct DSU{ vector<int> p,r; DSU(int n):p(n),r(n){ iota(p.begin(),p.end(),0);}
int f(int x){ return p[x]==x?x:p[x]=f(p[x]); }
bool u(int a,int b){ a=f(a); b=f(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; retu
};
int mst(int n, vector<vector<int>>& edges){
struct E{int u,v,w;}; vector<E> es;
for(auto &e: edges) es.push_back({e[0],e[1],e[2]});
sort(es.begin(), es.end(), [](auto &a, auto &b){return a.w<b.w;});
DSU d(n); long long cost=0; int used=0;
for(auto &e: es) if(d.u(e.u,e.v)){ cost+=e.w; used++; if(used==n-1) break; }
return used==n-1? (int)cost : -1;
}

P15. Critical Connections (Bridges)

Return all bridges in an undirected graph.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& edges){
 vector<vector<int>> g(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
vector<int> tin(n,-1), low(n,-1); int timer=0;
vector<vector<int>> res;
function<void(int,int)> dfs = [&](int u,int p){
tin[u]=low[u]=timer++;
for(int v: g[u]){
if(v==p) continue;
if(tin[v]!=-1){
low[u]=min(low[u], tin[v]);
}else{
dfs(v,u);
low[u]=min(low[u], low[v]);
if(low[v] > tin[u]) res.push_back({u,v});
}
}
};
for(int i=0;i<n;++i) if(tin[i]==-1) dfs(i,-1);
return res;
}

P16. Articulation Points

Return all articulation points in an undirected graph.
#include <bits/stdc++.h>
using namespace std;
vector<int> articulationPoints(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
vector<int> tin(n,-1), low(n,-1), isart(n,0); int timer=0;
function<void(int,int)> dfs = [&](int u,int p){
tin[u]=low[u]=timer++; int children=0;
for(int v: g[u]){
if(v==p) continue;
if(tin[v]!=-1) low[u]=min(low[u], tin[v]);
else{
dfs(v,u); low[u]=min(low[u], low[v]);
if(p!=-1 && low[v] >= tin[u]) isart[u]=1;
children++;
}
}
if(p==-1 && children>1) isart[u]=1;
};
for(int i=0;i<n;++i) if(tin[i]==-1) dfs(i,-1);
vector<int> res; for(int i=0;i<n;++i) if(isart[i]) res.push_back(i);
return res;
}

P17. Course Schedule II (Return Order)

Return one valid course order using Kahn's algorithm.
#include <bits/stdc++.h>
using namespace std;
vector<int> findOrder(int n, vector<vector<int>>& pre){
vector<vector<int>> g(n); vector<int> indeg(n);
for(auto &p: pre){ g[p[1]].push_back(p[0]); indeg[p[0]]++; }
queue<int> q; for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i);
vector<int> order;
while(!q.empty()){
int u=q.front(); q.pop(); order.push_back(u);
for(int v: g[u]) if(--indeg[v]==0) q.push(v);
}
if((int)order.size()!=n) return {};
return order;
}

P18. Longest Path in DAG

Given DAG with weighted edges, return the maximum path sum from source s.
#include <bits/stdc++.h>
using namespace std;
long long longestPathDAG(int n, vector<vector<int>>& edges, int s){
vector<vector<pair<int,int>>> g(n);
for(auto &e: edges) g[e[0]].push_back({e[1], e[2]});
// topo
vector<int> indeg(n);
for(int u=0;u<n;++u) for(auto [v,w]: g[u]) indeg[v]++;
queue<int> q; for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i);
vector<int> topo;
while(!q.empty()){ int u=q.front(); q.pop(); topo.push_back(u);
for(auto [v,w]: g[u]) if(--indeg[v]==0) q.push(v); }
 const long long NEG = -(1LL<<60);
vector<long long> dp(n, NEG); dp[s]=0;
for(int u: topo){
if(dp[u]==NEG) continue;
for(auto [v,w]: g[u]) dp[v]=max(dp[v], dp[u]+w);
}
long long ans = *max_element(dp.begin(), dp.end());
return ans;
}

P19. 0-1 BFS Shortest Path

Graph with edges weight 0/1. Return shortest distance from s to all nodes.
#include <bits/stdc++.h>
using namespace std;
vector<int> zeroOne(int n, vector<vector<int>>& edges, int s){
vector<vector<pair<int,int>>> g(n);
for(auto &e: edges) g[e[0]].push_back({e[1], e[2]}), g[e[1]].push_back({e[0], e[2]});
const int INF=1e9; deque<int> dq; vector<int> dist(n, INF);
dist[s]=0; dq.push_front(s);
while(!dq.empty()){
int u=dq.front(); dq.pop_front();
for(auto [v,w]: g[u]){
int nd=dist[u]+w;
if(nd<dist[v]){
dist[v]=nd;
if(w==0) dq.push_front(v); else dq.push_back(v);
}
}
}
return dist;
}

P20. Count Strongly Connected Components

Return number of SCCs via Kosaraju.
#include <bits/stdc++.h>
using namespace std;
int countSCC(int n, vector<vector<int>>& edges){
vector<vector<int>> g(n), rg(n);
for(auto &e: edges){ g[e[0]].push_back(e[1]); rg[e[1]].push_back(e[0]); }
vector<int> vis(n,0), order;
function<void(int)> dfs1=[&](int u){
vis[u]=1; for(int v: g[u]) if(!vis[v]) dfs1(v); order.push_back(u);
};
for(int i=0;i<n;++i) if(!vis[i]) dfs1(i);
reverse(order.begin(), order.end());
vector<int> comp(n,-1); int cid=0;
function<void(int)> dfs2=[&](int u){
comp[u]=cid; for(int v: rg[u]) if(comp[v]==-1) dfs2(v);
};
for(int u: order) if(comp[u]==-1){ dfs2(u); cid++; }
return cid;
}
Complexity Summary (Quick Reference)
Algorithm Time Space Notes

DFS O(N+M) O(N) Recursion stack O(N) worst-case

BFS O(N+M) O(N) Shortest edges in unweighted graph

Topological Sort (Kahn/DFS) O(N+M) O(N) DAG only

Cycle Undirected (DFS) O(N+M) O(N) Parent tracking

Cycle Directed (Coloring) O(N+M) O(N) Stack coloring

Bipartite (BFS) O(N+M) O(N) 2-coloring

DAG Shortest Path O(N+M) O(N) Topo order relaxations

Dijkstra (heap) O((N+M) log N) O(N) Non-negative weights

0-1 BFS O(N+M) O(N) Edge weights ∈{0,1}

Bellman-Ford O(N*M) O(N) Detects negative cycles

Floyd–Warshall O(N^3) O(N^2) All-pairs

DSU (Union/Find) ~O(α(N)) per op O(N) Path compression+rank

MST Kruskal O(M log M) O(N) Sort edges + DSU

MST Prim O(M log N) O(N) Heap-based

SCC (Kosaraju) O(N+M) O(N+M) Two DFS passes

Bridges/Articulation O(N+M) O(N) Low-link values

Multi-source BFS O(N+M) O(N) Init queue with all sources

Grid BFS O(N*M) O(N*M) 4-directional moves

N = number of nodes, M = number of edges.