10510 - Cactus

[serur]

After deciding whether the graph is strongly connected, we need to check if it is singly connected: there are no two simple paths
sharing the same origin and the same end...

[Imti]

Just check whether graph is strongly connected and then check whether graph have any cross or forward edge.If first one is 'yes' and second one is 'no' then the graph is cactus otherwise not.no need to check something else.Here's some case.

Code: Select all

2
5
7
0 1
1 2
2 0
2 3
3 2
2 4
4 2
5
8
0 1
1 2
2 0
2 3
3 2
2 4
4 2
0 4

output:

Code: Select all

YES
NO