Graph Algorithms — From Basics to Advanced
Graphs are one of the most important topics in competitive programming.
Many problems that look completely different on the surface can actually be modeled as a graph:
- Cities connected by roads
- Computers connected by networks
- People connected through relationships
- Courses connected by prerequisites
- States connected by transitions
- Cells connected in a grid
- Websites connected by links
Once we recognize the vertices and edges, the problem often becomes much easier.
This blog is a complete guide to graph algorithms for competitive programming, especially useful for Codeforces.
1. What Is a Graph?
A graph consists of:
- Vertices (Nodes) — the objects
- Edges — connections between objects
We usually represent a graph as:
where:
- (V) = set of vertices
- (E) = set of edges
For example:
1 ----- 2
| |
| |
3 ----- 4
Here:
Vertices = {1, 2, 3, 4}
Edges = {
(1,2),
(1,3),
(2,4),
(3,4)
}
2. Types of Graphs
Before choosing an algorithm, first identify what type of graph you have.
Undirected Graph
An edge works in both directions.
1 ----- 2
If we can go:
1 → 2
then we can also go:
2 → 1
Directed Graph
An edge has a direction.
1 -----> 2
We can go:
1 → 2
but not necessarily:
2 → 1
Weighted Graph
Every edge has a cost.
1 --5-- 2
The cost of going from 1 to 2 is 5.
Unweighted Graph
Edges don't have explicit weights.
1 ----- 2
Usually, every edge can be considered to have weight 1.
Cyclic Graph
A graph containing a cycle.
1 ---- 2
| |
| |
4 ---- 3
We can start at 1 and return to 1.
Acyclic Graph
A graph without cycles.
A directed acyclic graph is called a:
DAG — Directed Acyclic Graph
3. Important Terminology
Degree
For an undirected graph:
degree(v) = number of edges connected to v
For directed graphs:
- indegree = incoming edges
- outdegree = outgoing edges
Example:
1 → 2 → 3
↑
|
4
For node 2:
indegree = 2
outdegree = 1
4. Path
A path is a sequence of vertices connected by edges.
1 → 2 → 5 → 7
Path length in an unweighted graph:
number of edges
Here:
length = 3
5. Cycle
A cycle is a path that starts and ends at the same vertex.
1 → 2 → 3 → 1
Cycle detection is one of the most common graph problems on Codeforces.
6. Connected Components
Consider:
1 -- 2 4 -- 5
| |
3 6
There are two connected components:
Component 1 = {1,2,3}
Component 2 = {4,5,6}
DFS or BFS can find connected components in:
7. Graph Representation
There are three common ways to represent graphs.
7.1 Adjacency Matrix
For:
1 ----- 2
|
|
3
we can use:
1 2 3
1 0 1 1
2 1 0 0
3 1 0 0
Complexity
Space:
Checking whether an edge exists:
Iterating through all neighbors:
When to use?
Usually when:
V is small
For example:
V ≤ 500
depending on memory limits.
7.2 Adjacency List
This is the most common representation in competitive programming.
For:
1 -- 2
| |
3 -- 4
we can store:
1: 2, 3
2: 1, 4
3: 1, 4
4: 2, 3
In C++:
vector<vector<int>> graph(n + 1);
graph[u].push_back(v);
graph[v].push_back(u);
For a directed graph:
graph[u].push_back(v);
Complexity
Space:
This is generally the best representation for Codeforces graph problems.
7.3 Edge List
Store edges directly:
vector<pair<int,int>> edges;
For weighted graphs:
struct Edge {
int u, v, w;
};
Useful for algorithms such as:
- Kruskal
- Bellman-Ford
- Some offline graph problems
8. Graph Representation Comparison
| Representation | Space | Check Edge | Find Neighbors | Best Use |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) | Small dense graphs |
| Adjacency List | O(V+E) | O(deg(v)) | O(deg(v)) | Most problems |
| Edge List | O(E) | O(E) | O(E) | Kruskal/Bellman-Ford |
Default choice in Codeforces:
Use an adjacency list unless there is a specific reason not to.
9. DFS — Depth First Search
DFS explores as far as possible before going back.
Example:
1
├── 2
│ ├── 4
│ └── 5
└── 3
A possible DFS order:
1 → 2 → 4 → 5 → 3
Recursive DFS
void dfs(int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
Complexity
Every vertex is visited once.
Every edge is processed a constant number of times.
Therefore:
Space:
for the visited array and recursion stack.
10. BFS — Breadth First Search
BFS explores the graph level by level.
Level 0: 1
Level 1: 2 3
Level 2: 4 5 6
Implementation:
queue<int> q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
Complexity:
11. DFS vs BFS
| Feature | DFS | BFS |
|---|---|---|
| Data structure | Stack / recursion | Queue |
| Traversal | Deep first | Level first |
| Connected components | Yes | Yes |
| Cycle detection | Yes | Yes |
| Unweighted shortest path | Not naturally | Yes |
| Tree depth problems | Excellent | Good |
| Level-order problems | Not ideal | Excellent |
Easy rule
If the problem asks:
"Minimum number of edges?"
Think:
BFS
If the problem asks:
"Explore / components / recursion / structure?"
Think:
DFS
12. BFS for Shortest Path
In an unweighted graph, BFS gives the shortest path in terms of number of edges.
Example:
1 -- 2 -- 4
| |
3 --------
From 1 to 4:
1 → 2 → 4
Distance:
2
Implementation:
vector<int> dist(n + 1, -1);
queue<int> q;
dist[src] = 0;
q.push(src);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
Complexity:
13. Multi-Source BFS
Sometimes there are multiple starting points.
Example:
Sources = {1, 5, 8}
Instead of running BFS three times, put all sources into the queue initially.
for (int src : sources) {
dist[src] = 0;
q.push(src);
}
Then perform normal BFS.
Complexity:
This is extremely useful in grid problems and shortest-distance-to-nearest-source problems.
14. 0-1 BFS
What if edge weights are only:
0 or 1
Example:
u --0-- v
u --1-- x
Dijkstra works, but 0-1 BFS is faster and simpler.
Use a:
deque<int>
Rules:
- Weight
0→ push to front - Weight
1→ push to back
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (w == 0)
dq.push_front(v);
else
dq.push_back(v);
}
Complexity:
15. Dijkstra's Algorithm
Dijkstra finds shortest paths from one source when:
All edge weights are non-negative.
Example:
1 --4-- 2
| |
2 1
| |
3 --5-- 4
We maintain:
dist[v] = shortest known distance from source to v
The key idea:
Always process the currently closest unprocessed vertex.
With a priority queue:
priority_queue<
pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>
> pq;
Implementation:
vector<long long> dist(n + 1, INF);
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u])
continue;
for (auto [v, w] : graph[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
Complexity:
Usually written as:
for connected sparse graphs.
16. Why Dijkstra Does NOT Work With Negative Edges
Suppose:
A → B = 5
A → C = 2
C → B = -10
Dijkstra might finalize B with:
5
before discovering:
A → C → B
= 2 - 10
= -8
Therefore:
Dijkstra requires non-negative edge weights.
17. Bellman-Ford
Bellman-Ford handles:
- Positive edges
- Zero edges
- Negative edges
- Negative cycle detection
The basic idea is to relax every edge repeatedly.
For every edge:
u → v with weight w
perform:
dist[v] = min(dist[v], dist[u] + w);
Repeat:
V - 1 times
Complexity:
This is much slower than Dijkstra.
18. Negative Cycle Detection
After performing V - 1 relaxations, perform one more iteration.
If a distance can still be improved:
negative cycle exists
Why?
A shortest simple path can contain at most:
V - 1 edges
If we still improve after that, a cycle must be involved.
19. Floyd-Warshall
What if we need shortest paths between:
Every pair of vertices?
Use Floyd-Warshall.
We maintain:
dist[i][j]
and try every vertex k as an intermediate vertex:
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] =
min(dist[i][j],
dist[i][k] + dist[k][j]);
}
}
}
Complexity:
Space:
Best when:
V is small
20. Shortest Path Algorithm Decision
This is one of the most important things to remember.
| Graph | Algorithm | Complexity |
|---|---|---|
| Unweighted | BFS | O(V+E) |
| Weights are 0/1 | 0-1 BFS | O(V+E) |
| Non-negative weights | Dijkstra | O(E log V) |
| Negative weights | Bellman-Ford | O(VE) |
| All-pairs shortest path, small V | Floyd-Warshall | O(V³) |
Quick decision tree
Shortest Path
|
├── Unweighted?
│ └── BFS
|
├── Weights only 0/1?
│ └── 0-1 BFS
|
├── Any negative edge?
│ ├── Yes → Bellman-Ford
│ └── No → Dijkstra
|
└── All pairs + small V?
└── Floyd-Warshall
21. DSU — Disjoint Set Union
DSU is also called:
Union-Find
It maintains multiple disjoint sets.
Initially:
1 2 3 4 5
Every node is its own component.
If we perform:
union(1,2)
union(2,3)
we get:
{1,2,3} {4} {5}
22. DSU Operations
Two main operations:
Find
Find the representative of a set.
find(x)
Union
Merge two sets.
union(a,b)
With:
- Path compression
- Union by size/rank
the amortized complexity is:
where (\alpha) is the inverse Ackermann function.
For practical purposes:
Almost constant time.
23. Kruskal's Algorithm
Kruskal finds a:
Minimum Spanning Tree (MST)
for a connected weighted undirected graph.
The idea:
- Sort edges by weight.
- Take the smallest edge.
- If it doesn't create a cycle, add it.
- Otherwise skip it.
- Continue until we have
V-1edges.
Example:
Edges:
1 -- 1 -- 2
2 -- 2 -- 3
1 -- 5 -- 3
Choose:
weight 1
weight 2
Total:
3
Kruskal + DSU
This is where DSU becomes extremely useful.
For an edge:
u -- v
if:
find(u) != find(v)
then adding the edge won't create a cycle.
Then:
unite(u, v);
Complexity:
Sorting:
DSU operations:
Overall:
24. Prim's Algorithm
Prim also finds an MST.
Instead of sorting all edges, it grows the MST from one starting vertex.
With a priority queue:
Both Prim and Kruskal solve the same problem but work differently.
25. Kruskal vs Prim
| Feature | Kruskal | Prim |
|---|---|---|
| Main idea | Choose smallest edges | Grow tree |
| Main data structure | DSU | Priority Queue |
| Complexity | O(E log E) | O(E log V) |
| Best for | Edge-list problems | Adjacency-list problems |
| Handles disconnected graph | Gives minimum spanning forest | Needs handling per component |
Practical Codeforces rule
If the graph is naturally given as:
list of edges
Kruskal + DSU is often very convenient.
26. Topological Sort
Topological sorting is possible only for:
Directed Acyclic Graphs (DAGs)
It gives an ordering such that:
For every edge:
u → v
u appears before v.
Example:
1 → 3
2 → 3
3 → 4
Valid ordering:
1 2 3 4
or:
2 1 3 4
27. Kahn's Algorithm
Kahn's algorithm uses indegrees.
First calculate:
indegree[v]
Put all nodes with:
indegree = 0
into a queue.
Then:
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0)
q.push(v);
}
}
If:
order.size() < V
then the graph contains a cycle.
Complexity:
28. DFS Topological Sort
Topological sorting can also be done with DFS.
The important idea:
Add a node after processing all its outgoing edges.
Then reverse the resulting list.
Complexity:
29. DAG Dynamic Programming
One of the most useful combinations is:
Topological Sort + DP
For example:
Find the longest path in a DAG.
Process nodes in topological order.
For every edge:
u → v
update:
dp[v] = max(dp[v], dp[u] + weight);
Complexity:
This is much faster than general shortest/longest path approaches because DAGs have no cycles.
30. Bipartite Graph
A graph is bipartite if we can divide its vertices into two groups such that:
No edge connects vertices inside the same group.
Example:
Group A: 1 3 5
Group B: 2 4 6
Every edge goes:
A ↔ B
31. Checking Bipartite Graph
Use BFS or DFS with two colors.
color[src] = 0;
queue<int> q;
q.push(src);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
}
else if (color[v] == color[u]) {
return false;
}
}
}
Complexity:
Important fact
An undirected graph is bipartite iff it contains no odd-length cycle.
32. Cycle Detection in Undirected Graph
Using DFS:
bool dfs(int u, int parent) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
if (dfs(v, u))
return true;
}
else if (v != parent) {
return true;
}
}
return false;
}
Complexity:
33. Cycle Detection in Directed Graph
For directed graphs, simply checking visited[v] isn't enough.
We need to know whether a node is currently in the recursion path.
Use three states:
0 = unvisited
1 = currently visiting
2 = completely processed
If we find an edge:
u → v
where:
state[v] == 1
then we found a cycle.
Complexity:
34. Strongly Connected Components
For directed graphs, two vertices belong to the same strongly connected component if:
u → v
and:
v → u
are both possible.
Example:
1 → 2
↑ ↓
4 ← 3
All four nodes can reach each other.
Therefore:
{1,2,3,4}
is one SCC.
35. Kosaraju's Algorithm
Kosaraju finds SCCs in:
It uses two DFS passes.
Step 1
Run DFS on the original graph and store nodes by finishing time.
Step 2
Reverse every edge.
Step 3
Process vertices in decreasing finishing-time order.
Each DFS in the reversed graph gives one SCC.
36. Tarjan's SCC Algorithm
Tarjan finds SCCs using a single DFS.
It maintains:
discovery time
low-link value
stack
Complexity:
Kosaraju is often easier to implement and understand.
Tarjan is more advanced and useful when you want a one-pass SCC algorithm.
37. Condensation Graph
After finding SCCs, we can compress every SCC into a single node.
Example:
SCC A → SCC B → SCC C
The resulting graph is always a:
DAG
This technique is extremely useful.
A common Codeforces pattern is:
Original graph
↓
Find SCC
↓
Compress SCCs
↓
DAG
↓
DP / Topological Sort
38. Bridges
A bridge is an edge whose removal increases the number of connected components.
Example:
1 -- 2 -- 3
The edge:
2 -- 3
is a bridge.
But in:
1
|\
| \
2--3
none of the triangle edges is a bridge.
39. Finding Bridges
Use DFS with:
tin[u] = discovery time
low[u] = earliest reachable discovery time
For a DFS tree edge:
u → v
if:
then:
(u,v) is a bridge
Complexity:
40. Articulation Points
An articulation point is a vertex whose removal increases the number of connected components.
Example:
1 -- 2 -- 3
|
4
Removing 2 disconnects the graph.
So:
2 = articulation point
Using the same tin and low concepts, articulation points can be found in:
41. Bridges vs Articulation Points
| Concept | Remove | Result |
|---|---|---|
| Bridge | Edge | Components increase |
| Articulation Point | Vertex | Components increase |
Both can be found using DFS + low-link values.
42. Euler Path and Euler Circuit
An Euler path uses every edge exactly once.
An Euler circuit uses every edge exactly once and returns to the starting vertex.
For an undirected graph:
Euler Circuit
Every vertex has even degree.
Euler Path
Exactly two vertices have odd degree.
Special case:
0 odd-degree vertices
also gives an Euler circuit.
43. Hamiltonian vs Euler
Do not confuse these.
Euler
Visit every:
EDGE
exactly once.
Hamiltonian
Visit every:
VERTEX
exactly once.
Euler problems are often manageable.
Hamiltonian problems are generally much harder and often require special constraints or DP/bitmask techniques.
44. Maximum Flow
Some graph problems aren't about paths or connectivity.
They are about:
How much flow can move from source
sto sinkt?
Examples:
- Network capacity
- Matching
- Assigning resources
- Scheduling
- Cutting networks
Common algorithms:
- Ford-Fulkerson
- Edmonds-Karp
- Dinic
45. Dinic's Algorithm
Dinic works in phases:
- BFS builds a level graph.
- DFS sends blocking flow.
A standard implementation uses:
struct Edge {
int to;
long long cap;
int rev;
};
Complexity for general graphs is commonly given as:
although actual performance is often much better depending on the graph structure.
For Codeforces, Dinic is one of the most important max-flow implementations to know.
46. Matching
Many matching problems can be transformed into flow.
For bipartite matching:
Left side
|
↓
Edges
|
↓
Right side
A standard flow construction is:
Source
↓
Left vertices
↓
Possible matches
↓
Right vertices
↓
Sink
Each edge gets capacity 1.
Then:
maximum flow = maximum matching
47. Grid as a Graph
One of the biggest competitive-programming tricks:
A grid is often just a graph in disguise.
Example:
. . #
. . .
# . .
Each cell can be considered a vertex.
Edges connect neighboring cells.
For four-direction movement:
up
down
left
right
Then standard algorithms work:
BFS
DFS
0-1 BFS
Dijkstra
DSU
depending on the problem.
48. Grid BFS
For an unweighted grid:
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
Then:
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// validate cell
if (!visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
Complexity:
for an N × M grid.
49. DSU on Grids
DSU is useful when cells are dynamically connected.
For example:
Add land
Remove land
Connect components
Count islands
Map a cell:
(x, y)
to:
id = x * m + y
Then use normal DSU operations.
50. Binary Lifting on Trees
Trees are also graphs.
When queries ask:
What is the kth ancestor of node u?
or:
Find LCA of u and v.
Binary lifting is very useful.
Precompute:
up[u][j]
where:
up[u][j] = 2^j-th ancestor of u
Then:
preprocessing.
Each query:
51. LCA — Lowest Common Ancestor
For two nodes:
1
/ \
2 3
/ \
4 5
LCA of:
4 and 5
is:
2
LCA of:
4 and 3
is:
1
Common approaches:
- Binary lifting
- Euler tour + RMQ
- Heavy-Light Decomposition
52. Tree Diameter
The diameter of a tree is the longest path between any two vertices.
A simple method:
Step 1
Start BFS/DFS from any node.
Find the farthest node:
A
Step 2
Run BFS/DFS from A.
The farthest distance found is the diameter.
Complexity:
For a tree:
so this is effectively:
53. Heavy-Light Decomposition
Heavy-Light Decomposition, or HLD, is used for advanced tree queries.
It can convert tree path queries into a small number of array range queries.
Usually combined with:
- Segment Tree
- Fenwick Tree
Typical problems:
Update a node
Query path sum
Query path maximum
Update an edge
Query path minimum
Typical complexity:
Preprocessing:
Query:
when combined with a segment tree.
54. Graph Algorithm Complexity Cheat Sheet
Here is the important comparison.
| Algorithm | Problem | Complexity |
|---|---|---|
| DFS | Traversal | O(V+E) |
| BFS | Traversal | O(V+E) |
| Multi-source BFS | Shortest unweighted distance | O(V+E) |
| 0-1 BFS | Weights 0/1 | O(V+E) |
| Dijkstra | Non-negative weights | O(E log V) |
| Bellman-Ford | Negative weights | O(VE) |
| Floyd-Warshall | All-pairs shortest path | O(V³) |
| DSU | Dynamic connectivity | O(α(V)) amortized |
| Kruskal | MST | O(E log E) |
| Prim | MST | O(E log V) |
| Topological Sort | DAG ordering | O(V+E) |
| SCC — Kosaraju | Strong connectivity | O(V+E) |
| SCC — Tarjan | Strong connectivity | O(V+E) |
| Bridges | Critical edges | O(V+E) |
| Articulation Points | Critical vertices | O(V+E) |
| Tree Diameter | Longest tree path | O(V) |
| LCA + Binary Lifting | Ancestor queries | O(log V) per query |
| Dinic | Maximum flow | O(V²E) general bound |
| Floyd-Warshall | All-pairs | O(V³) |
55. The Most Important Decision Table
When you see a graph problem, ask these questions in order.
Question 1 — Is it a tree?
If:
Connected
+
V - 1 edges
then it's a tree.
Think about:
DFS
BFS
Tree DP
LCA
Diameter
HLD
Question 2 — Is it unweighted?
If yes and you need shortest distance:
BFS
Question 3 — Are weights only 0 and 1?
Use:
0-1 BFS
Question 4 — Are all weights non-negative?
Use:
Dijkstra
Question 5 — Are there negative weights?
Think:
Bellman-Ford
Question 6 — Do you need all-pairs shortest paths?
If V is small:
Floyd-Warshall
Question 7 — Do you need minimum spanning tree?
Think:
Kruskal + DSU
or:
Prim
Question 8 — Is it a DAG?
Think:
Topological Sort
+
DP
Question 9 — Is the graph directed and connectivity is complicated?
Think:
SCC
Question 10 — Does removing an edge disconnect the graph?
Think:
Bridge
Question 11 — Does removing a vertex disconnect the graph?
Think:
Articulation Point
Question 12 — Is the graph bipartite?
Think:
BFS/DFS + 2-coloring
Question 13 — Are you repeatedly joining components?
Think:
DSU
Question 14 — Is the problem about sending maximum capacity?
Think:
Max Flow
56. One Mental Map for Graph Algorithms
The easiest way to remember graph algorithms is not by memorizing code.
Memorize the problem → algorithm relationship.
GRAPH
|
┌───────────┴───────────┐
| |
UNDIRECTED DIRECTED
| |
┌───┴────┐ ┌────┴─────┐
| | | |
Unweighted Weighted DAG General
| | | |
BFS ┌┴────┐ Topo SCC
| |
0/1 Non-negative
| |
0-1 BFS Dijkstra
And for special problems:
Connectivity
↓
DFS / BFS / DSU
MST
↓
Kruskal / Prim
Critical edge
↓
Bridge
Critical vertex
↓
Articulation Point
All pairs shortest path
↓
Floyd-Warshall
Negative edges
↓
Bellman-Ford
Maximum capacity
↓
Max Flow
Tree queries
↓
LCA / HLD / Tree DP
57. How to Approach a Codeforces Graph Problem
Don't immediately start coding.
Use this process.
Step 1 — Identify the vertices
Ask:
What represents a node?
It could be:
city
person
cell
state
index
position
string
configuration
Step 2 — Identify the edges
Ask:
When can I move from one state to another?
For example:
city A → city B
or:
cell (x,y) → cell (nx,ny)
Step 3 — Check direction
Ask:
Can I travel both ways?
If yes:
Undirected
Otherwise:
Directed
Step 4 — Check weights
Ask:
Does every move have the same cost?
If yes:
BFS
If not:
Look at the weights.
Step 5 — Check constraints
This is extremely important.
For example:
V ≤ 20
allows completely different techniques from:
V ≤ 2 × 10^5
Never choose an algorithm without checking constraints.
58. Complexity Is Often the Real Answer
Suppose:
V = 2 × 10^5
E = 2 × 10^5
Then:
O(V²)
is impossible.
You probably want:
O(V+E)
or:
O(E log V)
But if:
V = 500
then:
O(V²)
might be completely fine.
So don't ask only:
"Which algorithm is better?"
Ask:
"Which algorithm fits the constraints?"
59. Common Graph Mistakes
Mistake 1 — Using DFS for unweighted shortest path
DFS can find a path, but it doesn't naturally give the shortest path.
Use:
BFS
Mistake 2 — Using Dijkstra with negative edges
Wrong.
Use:
Bellman-Ford
when negative edges genuinely need to be handled.
Mistake 3 — Forgetting disconnected components
If the graph may be disconnected:
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
}
}
Don't assume starting from node 1 visits everything.
Mistake 4 — Forgetting graph direction
These are completely different:
u → v
and:
u ↔ v
Mistake 5 — Integer overflow
Shortest paths can exceed int.
Prefer:
long long
for distances when constraints require it.
Mistake 6 — Recursion depth
A DFS on a chain:
1 → 2 → 3 → 4 → ... → 200000
may cause stack overflow in some environments.
For very deep graphs, consider:
iterative DFS
or an appropriately managed stack.
60. Graph Patterns Worth Memorizing
If you are preparing for Codeforces, these patterns are especially valuable.
Pattern 1
Unweighted shortest path
→ BFS
Pattern 2
Connected components
→ DFS/BFS
Pattern 3
0/1 edge weights
→ 0-1 BFS
Pattern 4
Positive weighted shortest path
→ Dijkstra
Pattern 5
Negative edges
→ Bellman-Ford
Pattern 6
Minimum spanning tree
→ Kruskal + DSU
Pattern 7
DAG + ordering
→ Topological Sort
Pattern 8
DAG + optimization
→ Topological Sort + DP
Pattern 9
Directed mutual reachability
→ SCC
Pattern 10
Critical edge
→ Bridge
Pattern 11
Critical vertex
→ Articulation Point
Pattern 12
Repeated component merging
→ DSU
Pattern 13
Tree ancestor queries
→ LCA
Pattern 14
Tree path queries
→ HLD
Pattern 15
Capacity / assignment
→ Max Flow
61. Final Graph Algorithm Cheat Sheet
GRAPH
|
┌───────────┴───────────┐
| |
Shortest Path Connectivity
| |
┌───┼───────┐ ┌────┼─────┐
| | | | | |
BFS 0-1 Dijkstra DFS BFS DSU
BFS
|
Negative?
|
Bellman-Ford
All pairs?
|
Floyd-Warshall
Minimum Spanning Tree
|
┌────┴────┐
Kruskal Prim
|
DSU
Directed Graph
|
┌──┴─────┐
DAG General
| |
Topo SCC
|
DP
Undirected Graph
|
┌───┴─────┐
Bridge Articulation
Point
Tree
|
├── Diameter
├── LCA
├── Binary Lifting
├── Tree DP
└── HLD
Capacity
|
Max Flow
|
Dinic
62. Final Takeaway
You do not need to memorize every graph algorithm at once.
First become extremely comfortable with:
1. Graph representation
2. DFS
3. BFS
4. Connected components
5. Cycle detection
6. Bipartite checking
7. Shortest path
8. Dijkstra
9. DSU
10. Kruskal
11. Topological Sort
Then move to:
12. 0-1 BFS
13. Bellman-Ford
14. SCC
15. Bridges
16. Articulation Points
17. Tree Diameter
18. LCA
Finally:
19. HLD
20. Max Flow
21. Advanced graph DP
22. Advanced tree algorithms
The most important skill is not remembering the implementation.
It is being able to look at a problem and say:
"This is actually a graph problem, and this is the graph algorithm that matches its structure and constraints."
Once you develop that skill, a large class of Codeforces problems becomes much easier to recognize and solve.
Quick Revision
BFS
→ Unweighted shortest path
DFS
→ Traversal / components / structure
0-1 BFS
→ Edge weights 0 or 1
Dijkstra
→ Non-negative weights
Bellman-Ford
→ Negative weights
Floyd-Warshall
→ All-pairs shortest path
DSU
→ Component merging
Kruskal
→ Minimum spanning tree
Prim
→ Minimum spanning tree
Topological Sort
→ DAG ordering
SCC
→ Strong connectivity in directed graphs
Bridge
→ Critical edge
Articulation Point
→ Critical vertex
LCA
→ Tree ancestor/path structure
HLD
→ Advanced tree path queries
Dinic
→ Maximum flow
Graph problems become much easier when you stop thinking of them as "graph problems" and start thinking in terms of patterns:
Shortest path?
Connectivity?
Cycle?
MST?
DAG?
SCC?
Critical edge?
Critical vertex?
Tree query?
Flow?
Identify the pattern first.
Then choose the algorithm.
That is the real graph skill in competitive programming.
Комментарии (0)
