Cycle detection

Cycle detection finds out whether a graph has a cycle, a path that comes back to the vertex it started from without using any edge twice, and prints one. It is a depth-first search with one extra check per edge, works for two-way and one-way edges, and runs in O(n + m) for $n$ vertices and $m$ edges. If you need a cycle whose edge lengths add up to a negative number, use Bellman–Ford instead.

Explanation

A small town has 5 crossroads joined by two-way streets. Does it have a cycle, a round trip that comes back to the crossroad it started from without using any street twice?

The search explores the town the way a depth-first search explores a maze. It marks each crossroad when it first gets there, keeps driving to a crossroad that isn't marked yet, and walks back when there is none. While it does this, watch the streets that lead to a marked crossroad.

Fig. 1. The street from 4 is the way the search came. The street from 5 to 2 is not.

The search went from 2 to 3 and then to 5, so the street from 5 back to 2 closes a round trip through 2, 3 and 5. The street from 4 back to 3 is just the way the search came.

A street to a marked crossroad, other than the street the search came by, closes a round trip.

Many towns have one-way streets. This one has 7 crossroads and 8 streets, and each street may be driven only in the direction of its arrow. Is there a round trip, and through which crossroads?

Fig. 2. Is there a round trip along the one-way streets?

With the same rule, the search goes from crossroad 1 to 2, to 4 and to 7. Crossroad 7 has no street out, so the search walks back to 4, 2 and 1, and then drives to crossroad 3. The street from 3 leads to crossroad 4. Crossroad 4 is marked, and the search didn't come from it, so the rule reports a round trip.

Fig. 3. The street from crossroad 3 leads to a marked crossroad.

Crossroad 4 has only one street, to crossroad 7, and no street leads out of 7. No drive from 4 ever gets back to 3. The rule reports a round trip that doesn't exist.

So the question is when a marked crossroad really leads back. The current route is the crossroads the search has driven through to get where it is and hasn't walked back from yet. In the two-way town, crossroad 2 was on the current route. The route led from 2 down to 5, where the search was, so the street from 5 to 2 closed a round trip. Crossroad 4 is not on the current route, which is now just 1 and 3. It was marked on an earlier branch, and the search has already tried every drive from 4 and walked back from it. If crossroad 3 could be reached from 4, the search would have reached it then.

A marked crossroad is either on the current route or finished, so each crossroad needs one of three states: not marked, on the current route, or finished. A street to a crossroad on the current route closes a round trip. A street to a finished crossroad never does. At crossroad 3, the street to 4 leads to a finished crossroad, so the search goes on. This is cycle detection with depth-first search: a DFS that keeps one of the three states for every crossroad and reports a round trip when a street leads into the current route.

Crossroad 1 joins the current route, shown in the boxes below the town.

Crossroad 2 is not marked yet, so the search drives from 1 to 2, and 2 joins the current route.

Crossroad 4 is not marked yet, so the search drives from 2 to 4, and 4 joins the current route.

Crossroad 7 is not marked yet, so the search drives from 4 to 7, and 7 joins the current route.

Every street from crossroad 7 is checked, so 7 is finished and the search walks back to 4.

Every street from crossroad 4 is checked, so 4 is finished and the search walks back to 2.

Every street from crossroad 2 is checked, so 2 is finished and the search walks back to 1.

Crossroad 3 is not marked yet, so the search drives from 1 to 3, and 3 joins the current route.

Crossroad 4 is finished, so the street from 3 to 4 changes nothing.

Crossroad 5 is not marked yet, so the search drives from 3 to 5, and 5 joins the current route.

Crossroad 6 is not marked yet, so the search drives from 5 to 6, and 6 joins the current route.

Crossroad 3 is on the current route, so the street from 6 to 3 closes the round trip 3, 5, 6.

1/12

Fig. 4. Step through the search with the buttons. Light blue crossroads are on the current route, also shown in the boxes below the town, and green crossroads are finished. A grey arrow is a street to a finished crossroad. A street into the current route closes a round trip.

The street from crossroad 6 leads back to crossroad 3, which is on the current route, so the search reports the round trip 3, 5, 6. The street from 3 to the finished crossroad 4 changed nothing.

Implementation

In code and in the proof we say vertex and edge, and a round trip is a cycle. A one-way street is a directed edge, so the graph is directed, and it is stored as an adjacency list, where adj[v] lists the vertices that edges from v lead to.

The walk is a recursive function dfs(v), as in the DFS article: going deeper is a call, and walking back is a return. The calls that have started and not yet returned are the current route. Each vertex has a state in state[v]: 0 if it is not marked, 1 while it is on the current route, and 2 when it is finished, that is, when dfs(v) has returned. To print the cycle, each vertex also keeps in parent[v] the vertex it was reached from.

1. Initialise: state[v] = 0 for every vertex. For each vertex v that is still in state 0, call dfs(v), as when counting components in the DFS article. A cycle may not be reachable from vertex 1 at all.

2. Mark it: dfs(v) sets state[v] = 1, so v joins the current route.

3. Expand its edges: for each edge from v to u, if state[u] == 0, set parent[u] = v and go deeper with dfs(u).

4. Check for a cycle: if state[u] == 1, the edge leads into the current route. Remember v and u and stop. If state[u] == 2, do nothing.

5. Walk back: when all edges of v are checked, set state[v] = 2 and return.

6. Stop when the outer loop ends, or as soon as a cycle is found.

7. Restore the cycle: start at v and follow parent until you reach u, then reverse the list.

Step 7 works because u is on the current route above v: the parent links of the route lead from v back up to u. In the graph of Fig. 2, step 4 fires at v = 6 and u = 3; Fig. 5 shows step 7.

Fig. 5. The parent links lead from vertex 6 back up the route to vertex 3. Reversed, they give the cycle in order.

The program reads n and m, then m lines u v: a one-way edge from u to v. Vertices are numbered from 1 to n. It prints NO if there is no cycle, and otherwise YES and the vertices of one cycle in order on the next line. For the graph in Fig. 2 the input is:

7 8
1 2
1 3
2 4
3 4
3 5
4 7
5 6
6 3

The comments name the steps above.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> state, parent;
int cycle_from = 0, cycle_to = 0;  // the edge that closes the cycle, 0 if none

void dfs(int v) {
    // mark it: v joins the current route
    state[v] = 1;

    // expand its edges
    for (int u : adj[v]) {
        if (state[u] == 0) {
            parent[u] = v;
            dfs(u);  // go deeper
            if (cycle_from != 0) return;  // stop: a cycle was found deeper
        } else if (state[u] == 1) {
            // check for a cycle: the edge leads into the current route
            cycle_from = v;
            cycle_to = u;
            return;  // stop
        }
        // state[u] == 2: u is finished, nothing to do
    }

    // walk back: v is finished
    state[v] = 2;
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // one-way: from u to v only
    }

    // initialise
    state.assign(n + 1, 0);
    parent.assign(n + 1, 0);
    for (int v = 1; v <= n && cycle_from == 0; v++) {
        if (state[v] == 0) dfs(v);
    }

    if (cycle_from == 0) {
        cout << "NO\n";
        return 0;
    }

    // restore the cycle: follow parent from cycle_from up to cycle_to
    vector<int> cycle;
    for (int v = cycle_from; v != cycle_to; v = parent[v]) cycle.push_back(v);
    cycle.push_back(cycle_to);
    reverse(cycle.begin(), cycle.end());

    cout << "YES\n";
    for (int i = 0; i < (int)cycle.size(); i++) {
        cout << cycle[i] << (i + 1 < (int)cycle.size() ? ' ' : '\n');
    }
}

An edge from a vertex to itself is a cycle of one vertex. The code handles it: state[v] is 1 when the edge is checked, and the parent walk stops at once.

Each vertex enters the current route once and each edge is checked once, so the time is O(n + m). The memory is O(n + m) for the adjacency list, the arrays and the recursion, which is at most n calls deep.

Undirected graphs

In an undirected graph two states are enough: every edge to a marked vertex other than parent[v] closes a cycle. When the search first meets such an edge, at v, the other end u is still on the current route. If the search had already walked back from u, it would have checked the edge from u to v then, and either gone to v from u or found this edge first. So parent leads from v up to u.

The program adds each edge to both adj[u] and adj[v], and uses a bool array marked in place of state. The only change in the check is to skip the edge v was reached by, u == parent[v], before looking at marked[u]:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<bool> marked;
vector<int> parent;
int cycle_from = 0, cycle_to = 0;

void dfs(int v) {
    // mark it
    marked[v] = true;

    // expand its edges
    for (int u : adj[v]) {
        if (u == parent[v]) continue;  // the edge v came by
        if (!marked[u]) {
            parent[u] = v;
            dfs(u);  // go deeper
            if (cycle_from != 0) return;  // stop
        } else {
            // check for a cycle: a marked vertex v didn't come from
            cycle_from = v;
            cycle_to = u;
            return;  // stop
        }
    }
    // walk back
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // initialise
    marked.assign(n + 1, false);
    parent.assign(n + 1, 0);
    for (int v = 1; v <= n && cycle_from == 0; v++) {
        if (!marked[v]) dfs(v);
    }

    if (cycle_from == 0) {
        cout << "NO\n";
        return 0;
    }

    // restore the cycle
    vector<int> cycle;
    for (int v = cycle_from; v != cycle_to; v = parent[v]) cycle.push_back(v);
    cycle.push_back(cycle_to);
    reverse(cycle.begin(), cycle.end());

    cout << "YES\n";
    for (int i = 0; i < (int)cycle.size(); i++) {
        cout << cycle[i] << (i + 1 < (int)cycle.size() ? ' ' : '\n');
    }
}

For the graph in Fig. 1 the input is:

5 5
1 2
2 3
2 5
3 4
3 5

The program prints YES and the cycle 2, 3, 5. It must stop at the first cycle: if it went on, the edge between 2 and 5 would be found a second time from vertex 2, which is above 5 on the route, and parent doesn't lead from 2 to 5.

Correctness proof

The proof is for directed graphs. The invariant is: the vertices in state 1 are exactly the current route, and each of them was reached by an edge from the one before it.

If the program reports a cycle, the cycle is real. It reports one when dfs(v) checks an edge from $v$ to a vertex $u$ in state 1. Then $u$ is on the current route above $v$, and the route leads along edges from $u$ down to $v$. With the edge from $v$ back to $u$, it is a cycle.

If the graph has a cycle, the program reports one. Let $x$ be the first vertex of the cycle that the search marks, and $w$ the vertex before $x$ on the cycle, as in Fig. 6. When dfs(x) starts, every other vertex of the cycle is not marked yet. Follow the cycle from $x$. Suppose a vertex $c$ of the cycle is marked during dfs(x). Then dfs(c) checks the edge to the next vertex of the cycle before it returns, and so before dfs(x) returns. At that moment the next vertex is either not marked, and the search marks it now, or already marked. In the second case it was also marked during dfs(x), because it was not marked when dfs(x) started. Step by step, $w$ is marked during dfs(x), while $x$ is still on the current route. Then dfs(w) checks the edge from $w$ to $x$, finds $x$ in state 1 and reports a cycle, unless the program has already stopped at another cycle.

Fig. 6. Vertex 3 is the first vertex of the cycle that the search marks. Before it is finished, the search reaches vertex 6, and the edge from 6 leads back into the current route.

Edges into finished vertices can be skipped: the argument above never uses them.

Common mistakes

• Not skipping the edge you came by in an undirected graph, so every edge looks like a cycle, because the vertex the search came from is marked. Skip u == parent[v].

• Using the undirected rule in a directed graph, with one marked flag and a cycle for any marked neighbour, which reports a cycle at an edge into a finished vertex, such as the edge from 3 to 4 in Fig. 2. Use three states and report only an edge into state 1.

• Copying the parent skip into the directed code, which misses a cycle of two edges, such as from 1 to 2 and back. In a directed graph skip nothing.

• Starting the search only from vertex 1, which misses a cycle that can't be reached from it. Run dfs from every vertex still in state 0.

Similar algorithms

Topological sort answers "is there a cycle?" for a directed graph too: Kahn's algorithm takes fewer than $n$ vertices exactly when there is one. It doesn't give the cycle itself. When there is no cycle, the search here finishes every vertex, and the order in which they are finished, reversed, is a topological order. Without the edge from 6 to 3, the search in Fig. 2 finishes 7, 4, 2, 6, 5, 3, 1; reversed, 1 3 5 6 2 4 7 is a topological order.

A disjoint set union works for undirected graphs when edges are added one by one, with questions in between. An edge whose two ends are already in one set closes a cycle. It doesn't work for one-way edges.

Strongly connected components find every vertex of a directed graph that lies on some cycle, not just one cycle.

Counting all the different cycles of a graph is a different task. It needs backtracking over all paths and works only for small graphs.

Practice