Daily bit(e) of C++ | Longest cycle in a graph
Daily bit(e) of C++ #203, Common interview problem: Longest cycle in a graph.
Today we will look at a common C++ interview problem: Longest cycle in a graph.
Given a directed graph as std::vector<int>, where the value at index i represents the destination of an outgoing edge from i (-1 is used to represent no outgoing edges), determine the size of the longest cycle in the graph.
For example, the above graph is represented by {1,2,3,1,0}, forming a cycle of size three.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/4P3Pv8r9M.
Solution
We can decompose the problem into two parts: finding cycles and determining the size of the largest cycle.
To find cycles in a directed graph, we can use the topological sort algorithm that operates in O(n), processing all nodes that are not part of a cycle, leaving us with cycles.
Once we have executed the topological sort, we can traverse each remaining cycle, counting the number of nodes on this cycle (also O(n)).
