When we are using bfs to detect cycles , then there can be two approaches , first is that we maintain one parent array and check while traversing that the neighbour of current node which is visited and is not same as parent , then that means there is a cycle present .Another approach mentioned in this video is to maintain levels of every node instead of parent array . So in this case while traversing the neighbour we only need to check that the neighbour is visited and its level != curLevel-1 . This condition is sufficient , right ?
Cycle detection using bfs
In the code at 4961 , in the find_parents(), lines 36 and 37 are redundant , right because in main() , we have already found the parents and we are passing that only as the actual parameters to the make_union()
if you reach a visited node again then simplyy there is a cycle , else not
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.