10510 - Cactus

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10510 - Cactus

Post by serur » Wed Aug 12, 2009 10:23 am

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...
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10510 - Cactus

Post by Imti » Wed Nov 16, 2011 11:17 am

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

Post Reply

Return to “Volume 105 (10500-10599)”