# Determine if a vertex is a part of a cycle in O(m+n) complexity

I am trying to apply BFS to the following problem, but I'm not sure how to do it

Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$

Output: $true$, if $v$ is a part of a cycle, $false$ otherwise

Can someone explain in pseudocode or in words how to do this?

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Dec 4 '17 at 3:37
• @Lola1984: what will happen if your remove that node? Think about it. – noman pouigt Dec 4 '17 at 17:40

Simply apply Strongly connected components algorithm , Kosaraju's algorithm has complexity $O(m+n)$. Now, read through the SCC components and check if $v$ is part of a component with size $\geq$ 2. The second step is $O(n)$. Actually, the second step can be interleaved with the first step to get your required complexity result.