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...
10510 - Cactus
Moderator: Board moderators
Re: 10510 - Cactus
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Re: 10510 - Cactus
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.
output:
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
Code: Select all
YES
NO