Page 3 of 3

Re: 10510 - Cactus

Posted: Wed Aug 12, 2009 10:23 am
by 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...

Re: 10510 - Cactus

Posted: Wed Nov 16, 2011 11:17 am
by 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