LeetCode

Cycle Detection

How would you detect if there is a cycle?

https://en.wikipedia.org/wiki/Cycle_detection

Find Cycle

A simple way to detect the cycle is to walk in the graph (using DFS or BFS) and keep track of all nodes that have been visited. Once a node is visited for the second time, we can conclude that the node is the first node in the cycle (source: p.155 of CPHandbook). HOWEVER, THIS ONLY WORKS FOR Successor Graphs.

Why this doesn't work for Normal Graphs

The idea that visiting a node twice = cycle doesn’t work with a normal graph. In the graph below, node 4 is visited twice if you just do a walk, even though there is no cycle.

Drawing-2023-04-30

Thus, this only works with Successor Graph (the above is not a succ. graph because Node 3 has an outdegree of 2)

https://cp-algorithms.com/graph/finding-cycle.html

So you can still use DFS, but use a variation of the coloring algorithm. Initially all vertices are colored white (0). From each unvisited (white) vertex, start the DFS, mark it gray (1) while entering and mark it black (2) on exit. If DFS moves to a gray vertex, then we have found a cycle (if the graph is undirected, the edge to parent is not considered). The cycle itself can be reconstructed using parent array.

My implementation (without rebuilding the cycle), from https://leetcode.com/problems/course-schedule/

    int color[2001];
    vector<int> adj[2001];
    bool dfs(int i) {
        if (color[i] == 1) return false;
        if (color[i] == 2) return true;
        color[i] = 1;
        bool works = true;
        for (auto u: adj[i]) {
            works = works && dfs(u);
        }
        color[i] = 2;
        return works;
    }
    
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for (vector<int> prereq: prerequisites) {
            adj[prereq[0]].push_back(prereq[1]);
        }
        bool works = true;
        memset(color, 0, sizeof(color));
        for (int i=0;i<numCourses;i++) {
            works = works && dfs(i);
        }
        return works;
    }

Here is an implementation for directed graph (rebuilding the cycle)

int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;
 
bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u))
                return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}
 
void find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;
 
    for (int v = 0; v < n; v++) {
        if (color[v] == 0 && dfs(v))
            break;
    }
 
    if (cycle_start == -1) {
        cout << "Acyclic" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());
 
        cout << "Cycle found: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}

For Successor Graph

As stated above, we do DFS and then check that we don’t visit a node a second time. i That method uses $O(n)$ memory.

bool dfs(int i) {
	if (visited[i]) return false;
	visited[i] = true;
	bool works = true;
	for (auto u: adj[i]) {
		works = works && dfs(u);
	}
	return works;
}
 

However, If you want to optimize and only use $O(1)$ memory, you can use Floyd’s Cycle Finding Algorithm.

Floyd’s Algorithm

Floyd’s cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the “tortoise and the hare algorithm”, alluding to Aesop’s fable of The Tortoise and the Hare.

Floyd’s algorithm walks forward in the graph using two pointers a and b. Both pointers begin at a node x that is the starting node of the graph. Then, on each turn, the pointer a walks one step forward and the pointer b walks two steps forward. The process continues until the pointers meet each other:

a = succ(x);
b = succ(succ(x));
while (a != b) {
	a = succ(a);
	b = succ(succ(b));
}

At this point, the pointer a has walked k steps and the pointer b has walked 2k steps, so the length of the cycle divides k. Thus, the first node that belongs to the cycle can be found by moving the pointer a to node x and advancing the pointers step by step until they meet again.

 
a = x;
while (a != b) {
	a = succ(a);
	b = succ(b);
}
first = a;
 
// Calculate the length of the cycle
b = succ(a);
length = 1;
while (a != b) {
	b = succ(b);
	length++;
}
 
 

Longest Cycle in Graph

https://leetcode.com/problems/longest-cycle-in-a-graph/