$1$C

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

Example

Consider the example below:

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 trivial back edge discovered, use the DFS tree to figure out the nodes that must be on the cycle corresponding

to that back edge.

In $[60]$: def find$\_$all$\_$nodes$\_$in$\_$cycle$($g$)$: # $g$ is an UndirectedGraph class

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

# your code here

In $[61]$: #this is the example that we had for the problem.

g$3=$ UndirectedGraph$(8)$

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

g$3.$add$\_$edge $(,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 $(g3)$

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

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

# Let's also add the edge $6,7$

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

s$1=$ find$\_$all$\_$nodes$\_$in$\_$cycle $(g3)$

print$(f^{\text{'}}$ Your code returns set of nodes: $\{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{'})$