Chapter 22 of 30
Cycle Detection, Bipartite Checking & Topological Sort
Master cycle detection in undirected and directed graphs, bipartite checking, topological sort, and DAG reasoning.
Cycle Detection in Undirected GraphsCycle Detection in Directed GraphsBipartite CheckingTopological SortDAG ReasoningFunctional Graphs
Share:
Cycle Detection, Bipartite Checking & Topological Sort
These three techniques are the bread and butter of graph problems. Knowing when to apply each one — and understanding why it works — will help you solve a wide range of problems.
Cycle Detection in Undirected Graphs
DFS Approach
hljs cpp
vector<bool> visited(n, false);
bool hasCycle(int u, int parent) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
if (hasCycle(v, u)) return true;
} else if (v != parent) {
return true; // back edge → cycle
}
}
return false;
}
DSU Approach
hljs cpp
DSU dsu(n);
for (auto &[u, v] : edges) {
if (dsu.find(u) == dsu.find(v)) {
// cycle detected
} else {
dsu.unite(u, v);
}
}
Cycle Detection in Directed Graphs
DFS with Three States
hljs cpp
enum State { UNVISITED, IN_PROGRESS, DONE };
vector<State> state(n, UNVISITED);
bool hasCycle(int u) {
state[u] = IN_PROGRESS;
for (int v : adj[u]) {
if (state[v] == IN_PROGRESS) return true; // back edge → cycle
if (state[v] == UNVISITED && hasCycle(v)) return true;
}
state[u] = DONE;
return false;
}
Kahn's Algorithm (BFS Topological Sort)
If topological sort fails (not all nodes processed), there's a cycle:
hljs cpp
vector<int> inDegree(n, 0);
for (int u = 0; u < n; u++) {
for (int v : adj[u]) inDegree[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) q.push(i);
}
int processed = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
processed++;
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) q.push(v);
}
}
bool hasCycle = (processed != n);
Bipartite Checking
A graph is bipartite if you can 2-color it (no two adjacent nodes have the same color):
hljs cpp
vector<int> color(n, -1);
bool isBipartite(int start) {
queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1; // opposite color
q.push(v);
} else if (color[v] == color[u]) {
return false; // same color → not bipartite
}
}
}
return true;
}
// Check entire graph (may be disconnected)
bool bipartite = true;
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !isBipartite(i)) {
bipartite = false;
break;
}
}
Topological Sort
Linear ordering of vertices such that for every edge u → v, u comes before v:
Kahn's Algorithm (BFS)
hljs cpp
vector<int> topoSort;
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) q.push(i);
}
while (!q.empty()) {
int u = q.front(); q.pop();
topoSort.push_back(u);
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) q.push(v);
}
}
// If topoSort.size() == n, valid topological order exists
// Otherwise, the graph has a cycle
DFS Topological Sort
hljs cpp
vector<bool> visited(n, false);
vector<int> topoOrder;
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) dfs(v);
}
topoOrder.push_back(u); // post-order
}
// Run DFS from all unvisited nodes
for (int i = 0; i < n; i++) {
if (!visited[i]) dfs(i);
}
reverse(topoOrder.begin(), topoOrder.end());
DAG Reasoning
Topological sort enables DP on DAGs:
hljs cpp
// Longest path in a DAG
vector<int> dist(n, 0);
for (int u : topoOrder) {
for (int v : adj[u]) {
dist[v] = max(dist[v], dist[u] + weight[u][v]);
}
}
Functional Graphs
Every node has exactly one outgoing edge. These graphs consist of cycles with trees feeding into them.
hljs cpp
// Find the cycle in a functional graph
vector<int> nxt(n); // nxt[i] = the node i points to
vector<int> state(n, 0); // 0 = unvisited, 1 = in progress, 2 = done
vector<int> cycle;
void findCycle(int u) {
state[u] = 1;
int v = nxt[u];
if (state[v] == 0) {
findCycle(v);
} else if (state[v] == 1) {
// found cycle: from v to u
int cur = v;
do {
cycle.push_back(cur);
cur = nxt[cur];
} while (cur != v);
}
state[u] = 2;
}
Summary
- Undirected cycle: DFS with parent tracking, or DSU
- Directed cycle: DFS with three states, or Kahn's algorithm
- Bipartite: BFS 2-coloring
- Topological sort: Kahn's (BFS) or DFS post-order
- DAG + topological order = DP on DAGs
- Functional graphs: every node has exactly one outgoing edge → cycles with trees
Prefer reading offline? Download the full book as a PDF.
Download Free Book