/* ->pass currvertex and it's parent as -1 as argument to the dfs function ->traverse for thr adjancy list of the curr vertex ->if child is not visited --> call dfs ans pass child and it's parent as curr vertex ->if child is visisited ->if that child is not parent --> return true ->return false Here,basically we are checking the back edge */ vector g[100001]; vector visi(100001, 0); // -->cycle detection for undirected graph bool check_cycle(ll v, ll p) { visi[v] = true; for (ll child : g[v]) { if (visi[child] == false) { if(check_cycle(child, v)==true) return true; } else { if (child != p) return true; } } return false; } //here,p passed in a dfs function is a parent of a 'v' node,at start we pass dfs(v,-1);
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter