$**$Please help with the code. no need to creat new class as I've already have one in previous section. Thanks!$**$

We now wish to find the set of all nodes in the graph that belong to some cycle.

Example

Consider the example below: Zimage$-2.$png

Nodes $\{0,2,3,4\}$ lie on some cycle: example node $4$ lies on many cycles one such cycle being $2-3-4.$ whereas the other nodes do not.

Note We do not treat undirected edges as cycles although in our data structure, when an undirected edge $(i,j)$ is represented as two "directed"

edges $(i,j)$ and $(j,i),$ it gives the impression that they are in a cycle of length $2.$

Complete the function find$\_$all$\_$nodes$\_$in$\_$cycle that given a graph returns a python set of nodes in a cycle.

Hint Perform a DFS traversal and for each non trivia$/$back edge discovered, use the DFS tree to figure out the nodes that must be on the cycle

corresponding to that back edge.

def find$\_$all$\_$nodes$\_$in$\_$cycle$($g$)$: & g is an UndirectedGraph class

set$\_$of$\_$nodes $=$ set$()$

your code here

visited $=$ set$()$

parent $=$ dict$()$

def dfs$($node$,$ parent$\_$node$=$Hone$)$:

visited.add$($node$)$

parent$[$node$]=$ parent$\_$node

for neighbor in g$.$adj$\_$list$[$node$]$:

if neighbor not in visitedr

dfs$($neighbor$,$ node$)$

elif parent$\_$node $1=$ neighbor:

Add nodes to the set that are part of the cycle

cycle$\_$node $=$ node

while cycle$\_$node $1=$ neighbor:

set$\_$of$\_$nodes.add$($cycle$\_$node$)$

Check if the cycle$\_$node has a parent before accessing it

if cycle$\_$node in parent:

cycle$\_$node $=$ parent$[$cycle$\_$node$]$

else:

break # Exit the loop if no parent is found

set$\_$of$\_$nodes.add$($neighbor$)$

This line was causing the issue, adding node was creating a duplicate and Mone was being added to the set

$*$set$\_$of$\_$nodes,add$($node$)$

for node in range$($g$.$n$)$:

if node not in visited:

dfs $($node$)$

return set$\_$of$\_$nodes

$[77]$ this is the example that we had for the problem.

g$3=$ UndirectedGraph$(8)$

g$3.$add$\_$edge $(0,1)$

g$3.$add$\_$edge $(0,2)$

g$3.$add$\_$edge $(0,4)$

g$3.$add$\_$edge $(2,3)$

g$3.$add$\_$edge $(2,4)$

g$3.$ add$\_$edge $(3,4)$

g$3.$ add$\_$edge $(5,6)$

g$3.$add$\_$edge $(5,7)$

s $=$ find$\_$all$\_$nodes$\_$in$\_$cycle$($g$3)$

print$($f$\text{'}$Your code returns set of nodes : $($s$)\text{'})$

let's also add the edge $6,7$

g$3.$add$\_$edge $(6,7)$

s $1-$ find$\_$all$\_$nodes$\_$in$\_$cycle$($g$3)$

print$($f$\text{'}$Your code returns set of nodes $\{$:$f(s1{\}}^{\text{'}})$

assert $s1=\{0,2,3,4,5,6,7\},$ 'Fail: Set of nodes must be $\{0,2,3,4,5,6,7\}.\text{'}$

print$(\text{'}$All tests passedd: $10$ points!$\text{'})$

$\backslash$ Your code returns set of nodes: $\{0,2,3,4,$ None$\}$

$\backslash$ow code returns set of nodes: $\{0,2,3,4,$ None $\}$

AssertionBrror Traceback $($most recent call last$)$