CareerCup

tortoise and hare algorithm to detect circle.
then go reverse to find the beginning node.

or just use hashmap, insert into the map and wait for the first collision happen

@dexter
cn u pls write a pseudocode for this

DFS is the correct and optimal answer.
Initialise all nodes with white color
Visit a node color it grey, continue with its connected nodes
while doing so if u find the visiting node grey then the its cyclic

I know that I might sound stupid for asking, but what do you mean by "WAP" at the beginning of the original post?

I know that I might sound stupid for asking, but what do you mean by "WAP" at the beginning of the original post?

WAP -> Write a program

we can use a modification of the kruskal's algorithm to find the minimum spanning tree.
We can set every node in the graph as an independent set and sort the edges
for every edge in the list we check if both the ends are in the separate set, if u=yes then we merge
If we encounter an edge whose both ends are already in the same end, then we found the cycle.

For set operations we can use a Union-find data structure

Minimum spanning tree. Just do DFS, and assign each edge same weight (1). If the cost any time increase the maximum possible cost (all edges being traversed, there is a cycle.

DFS is the correct one.
Initialize all nodes with white color.
Visit a node, color it gret, continue with its connected nodes.
while doing so if u find the visiting node grey then the its cyclic.