Can you start from some node and come back to it? In a directed graph a cycle means that tasks depend on one another in a circle and that there is no valid order of execution. A graph without cycles is a DAG (a directed acyclic graph). Here are three ways to check: DFS with colours, Kahn's algorithm and a check for an undirected graph.
Before you start: prerequisites – BFS and DFS, topological sorting. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
A directed graph: DFS with three colours
Every node is in one of three states:
0 – white: not visited yet;
1 – grey: DFS has entered the node and has not finished with it yet (the node is on the current path);
2 – black: the node and everything reachable from it has been processed.
If from a grey node we come across a grey node, we have come back to the current path – that is a cycle. An edge to a black node is not a cycle (we have already been there along another path).
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<int> color; // 0 white, 1 grey, 2 black
bool hasCycle(int v) {
color[v] = 1; // v is on the current path
for (int u : graph[v]) {
if (color[u] == 1) return true; // we came back to the path: a cycle
if (color[u] == 0 && hasCycle(u)) return true;
}
color[v] = 2; // we have finished with v
return false;
}
int main() {
int n, m;
cin >> n >> m;
graph.resize(n + 1);
color.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v); // a directed edge u -> v
}
bool cycle = false;
for (int v = 1; v <= n && !cycle; v++)
if (color[v] == 0 && hasCycle(v)) cycle = true;
cout << (cycle ? "CYCLE" : "NO CYCLE") << endl;
return 0;
}
Example 1 – input
4 4
1 2
2 3
3 4
4 2
Output
CYCLE
Example 2 – input
4 4
1 2
1 3
2 4
3 4
Output
NO CYCLE
The second example shows why the third colour is needed: node 4 is reached twice (through 2 and through 3), but that is not a cycle – when we arrive the second time, node 4 is already black.
A directed graph: Kahn's algorithm
A node that has no incoming edges (in-degree 0) can be "executed" first. We remove such nodes one by one together with their edges, as in topological sorting. If some nodes are left unremoved at the end, they are on a cycle (none of them ever gets in-degree 0).
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> inDegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
inDegree[v]++;
}
queue<int> q;
for (int v = 1; v <= n; v++)
if (inDegree[v] == 0) q.push(v);
int removed = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
removed++;
for (int u : graph[v])
if (--inDegree[u] == 0) q.push(u); // u has no more incoming edges
}
cout << (removed < n ? "CYCLE" : "NO CYCLE") << endl;
return 0;
}
Kahn's algorithm has no recursion and gives a topological order along the way. DFS with colours makes it easier to return the cycle itself (see task 1).
An undirected graph
In an undirected graph every edge is seen in both directions, so "going back" to the node we have just come from is not a cycle. That is why we pass the parent to DFS: a cycle exists if we come across an already visited node that is not the parent. Another possibility: a connected undirected graph has a cycle exactly when it has at least n edges; in general, DSU is used – a cycle appears when an edge joins two nodes that are already in the same group.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
bool dfs(int v, int parent) {
visited[v] = true;
for (int u : graph[v]) {
if (u == parent) continue; // the edge we came along
if (visited[u]) return true; // visited, but not the parent: a cycle
if (dfs(u, v)) return true;
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
graph.resize(n + 1);
visited.assign(n + 1, false);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
bool cycle = false;
for (int v = 1; v <= n && !cycle; v++)
if (!visited[v] && dfs(v, 0)) cycle = true;
cout << (cycle ? "CYCLE" : "NO CYCLE") << endl;
return 0;
}
Which method to choose?
Situation
Method
a directed graph, only YES/NO is needed
Kahn or DFS with colours
a directed graph, the order is also needed (task scheduling)
Kahn – gives a topological order
a directed graph, the cycle must be printed
DFS with colours + a parent array
an undirected graph
DFS with the parent or DSU
edges arrive one by one, the question is when the first cycle appears
DSU
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: harder
Print the cycle
A directed graph is given. If it has a cycle, print the nodes of one cycle in order, so that the first node is repeated at the end (for example 2 3 4 2). Otherwise print NONE.
Example 1
Input
4 4
1 2
2 3
3 4
4 2
Output
2 3 4 2
Example 2
Input
3 2
1 2
2 3
Output
NONE
Hint
DFS with colours plus an array parent (the node from which we entered a node). When from v we come across a grey node u, the cycle is u → … → v → u: follow parent backwards from v until you reach u, then reverse.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> graph;
vector<int> color, parent;
int cycleStart = -1, cycleEnd = -1; // the cycle: cycleStart -> ... -> cycleEnd -> cycleStart
bool dfs(int v) {
color[v] = 1;
for (int u : graph[v]) {
if (color[u] == 1) { // we have found a cycle
cycleStart = u;
cycleEnd = v;
return true;
}
if (color[u] == 0) {
parent[u] = v;
if (dfs(u)) return true;
}
}
color[v] = 2;
return false;
}
int main() {
int n, m;
cin >> n >> m;
graph.resize(n + 1);
color.assign(n + 1, 0);
parent.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
for (int v = 1; v <= n && cycleStart == -1; v++)
if (color[v] == 0) dfs(v);
if (cycleStart == -1) {
cout << "NONE" << endl;
return 0;
}
vector<int> c;
c.push_back(cycleStart);
for (int v = cycleEnd; v != cycleStart; v = parent[v]) c.push_back(v);
c.push_back(cycleStart);
reverse(c.begin(), c.end());
for (size_t i = 0; i < c.size(); i++) cout << c[i] << (i + 1 < c.size() ? " " : "\n");
return 0;
}
TASK 02Difficulty: medium
A schedule of subjects
There are n subjects and m conditions of the form a b: the exam in subject a must be passed before the exam in subject b. Print one possible order of the exams (when there are several possibilities, always take the subject with the smallest number), or IMPOSSIBLE.
Example 1
Input
4 3
1 2
3 2
2 4
Output
1 3 2 4
Example 2
Input
2 2
1 2
2 1
Output
IMPOSSIBLE
Hint
Kahn's algorithm, but instead of an ordinary queue use a priority_queue with the smallest element on top, so that the smallest free subject is always taken. If not all the subjects have been scheduled – there is a cycle.
Solution (C++)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> inDegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
inDegree[b]++;
}
priority_queue<int, vector<int>, greater<int>> q; // the smallest on top
for (int v = 1; v <= n; v++)
if (inDegree[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int v = q.top();
q.pop();
order.push_back(v);
for (int u : graph[v])
if (--inDegree[u] == 0) q.push(u);
}
if ((int)order.size() < n) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
for (int i = 0; i < n; i++) cout << order[i] << (i + 1 < n ? " " : "\n");
return 0;
}
Common mistakes and tips
In a directed graph an ordinary array visited is not enough – three colours are needed.
In an undirected graph do not report a cycle for the edge you came along (the parent).
A graph can be disconnected: start the check from every unvisited node.
Check your knowledge
Open the quiz
Detecting cycles
1. What does it mean when DFS comes across a grey node from a grey node?
2. Kahn's algorithm removed 7 of 9 nodes. What does that mean?
3. What is a DAG?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.