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

Bilash
New poster
Posts: 3
Joined: Sat Oct 04, 2003 8:55 pm
Location: Sylhet, BANGLADESH
Contact:

Post by Bilash » Wed Dec 03, 2003 4:22 pm

Someone sent me some offline messages to know about Shorir's algo. Unfortunately, i deleted his/her name accidentally from my list :( . Can (s)he plz send his/her add again so that i can mail him/her?
Thanx!
Treat me like an angel and I will take you to heaven

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Mon Jan 19, 2004 6:51 am

Bilash wrote:Is finding cactus related to finding articulation points in a directed graph anyway? i think in a cactus, the simple cycles are connected to each other only through articulation vertices. i tried in this way, but still WA :cry:
Can anybody tell me the correct approach to solving this problem?
This is what I did... DFS, checking that there is exactly one back edge from any node that isn't root, no cross/forward edges (and that for each tree edge, dfsmin of the other end of the edge is the current node.

Saludos,
HoraPe

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Feb 19, 2004 6:05 am

horape wrote:
Bilash wrote:Is finding cactus related to finding articulation points in a directed graph anyway? i think in a cactus, the simple cycles are connected to each other only through articulation vertices. i tried in this way, but still WA :cry:
Can anybody tell me the correct approach to solving this problem?
This is what I did... DFS, checking that there is exactly one back edge from any node that isn't root, no cross/forward edges (and that for each tree edge, dfsmin of the other end of the edge is the current node.

Saludos,
HoraPe

I'm not very good at graph theory... what do you mean by cross/forward edge?

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Feb 19, 2004 1:14 pm

junbin wrote:
horape wrote:
Bilash wrote:Is finding cactus related to finding articulation points in a directed graph anyway? i think in a cactus, the simple cycles are connected to each other only through articulation vertices. i tried in this way, but still WA :cry:
Can anybody tell me the correct approach to solving this problem?
This is what I did... DFS, checking that there is exactly one back edge from any node that isn't root, no cross/forward edges (and that for each tree edge, dfsmin of the other end of the edge is the current node)
I'm not very good at graph theory... what do you mean by cross/forward edge?
Read on DFS, basically, when you run the DFS the edges get classified on tree edges (ones on the DFS tree), forward (from a node to a descendant on the DFS tree), back edges (from a node to an ascentor on the DFS tree) and cross edges (from a node on a dfs tree to a node on a different DFS tree, only exist on directed graphs)

dfsmin(v) is the vertex nearest to root for what there is a path from v that has only one back edge.

Hope this helps you,
HoraPe

Examiner
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm

10510 Test Case

Post by Examiner » Thu Feb 19, 2004 1:29 pm

Code: Select all

3
6
7
0 1
3 0
1 2
2 3
1 3
4 5
2 4
1
1
0 0
5
7
0 1
1 2
2 3
3 0
0 2
2 4
4 0

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 10510 Test Case

Post by CDiMa » Fri Feb 20, 2004 12:50 pm

Examiner wrote:

Code: Select all

3
6
7
0 1
3 0
1 2
2 3
1 3
4 5
2 4
1
1
0 0
5
7
0 1
1 2
2 3
3 0
0 2
2 4
4 0
The problem states that there aren't loops so your second test is incorrect
The other two tests aren't cacti.
The first one isn't strongly connected.
Both of them have edges that belong to two simple cycles
(for example edge 3 0 belongs to cycles 0 1 2 3 0 and 0 1 3 0 for the first one
and 0 1 2 3 0 and 0 2 3 0 for the last one)

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Mar 02, 2004 5:24 pm

marian wrote:Second possible solution can be repeatedly remove simple directed cycles. If graph contains some edges, but does not contain a cycle, it is not a cactus. If we successfully remove all the edges, given graph is a cactus. (because removed cycles had to be edge-disjoint (otherwise we could not remove some cycle)). I think, that by careful implementation, this could be done in O(n+m), too.
I don't think this is correct. This condition is necessary but not sufficient for a directed graph to be a cactus:

Code: Select all

1
3
6
0 1
1 0
1 2
2 1
2 0
0 2
Ciao!!!

Claudio

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Tue Feb 22, 2005 11:01 am

I think that:

First, check if the graph is strongly connected (I use Tarjan's algorithm)
Then use this observation:

A strongly connected graph is not a cactus if and only exist a pair u,v such that there are two of more paths from u to v (could anyone prove this clearly?)

we can prove: there is a pair u,v such that there are two of more paths from u to v if and only if:
(1) DFS tree has cross edge or forward edge
or (2) DFS tree has a vertex v such that there is two of more back edge to v or any ancestor of v

proof
if part: easy to see

only if part:

suppose there is a pair u,v suct that there are two of more paths from u to v

consider the time DFS enters u
- if v is exited, then there is a cross edge
- if v is not visited , then there is a cross edge or a forward edge
- if v is visited, but not exited, there is there is two of more back edge to v or any ancestor of v

I'm not sure my observation and my proof is correct. Could anyone have some comment.

(2) can check by : there exist a vertex v such that there is a back edge to v and low[v]<d[v]

but with the test cases of the judge, we don't need to care of back edge, just check if there is no cross/forward edge, we can got AC

Bilash wrote:
At last I got it AC
What i did is check that:
1. The indegree is equal to the out degree for each vertex
2. There is no forward or cross edge in the dfs tree of the graph
3. There is at most one back edge pointing to any particular vertex in the dfs tree.
By the way, i checked strong connectivity using Shorir's algo whose complexity is O(n).

I can't understand why
The indegree is equal to the out degree for each vertex?

Could anyone help me?

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Sep 25, 2005 6:02 am

Watch the special case, that for n=0 and n=1 the answer should be YES.

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

Cactus

Post by KvaLe » Thu Jan 19, 2006 8:44 pm

I've written this problem, but I think my program is wrong.
When I give this input it returns that given graph is cactus, but I think it isn't. Here is input:

Code: Select all

1
4
5
0 1
1 2
2 1
2 3
3 0
Here edge 0 -> 1 is in two cycle (0 -> 1 -> 2 -> 3 -> 0 and 1 -> 2 -> 1).

My algorithm is such:
1) Determine if the given graph is strongly connected. I'm doing it using Tarjan's algorithm. If graph isn't strongly connected answer is NO.
2) For each edge determine it's class (back, forward, cross or tree edge).
3) If we get one or more forward or cross edges the answer is NO, otherwise I'm checking if for any vertex u exists vertecies v and w, such that edge (u -> v) and edge (u -> w) is back edge answer is NO.
4) Then I'm checking if I haven't just printed NO I'm printing YES.

This is my algorithm, please check it and if u find bug please say me.

In that test, which I've wrote above there isn't any forward and cross edges, and there are only two back edges (2 -> 1 and 3 -> 0), so answer must be NO, but with my algorithm it's YES.
Giorgi Lekveishvili

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

AC

Post by KvaLe » Wed Jan 25, 2006 5:57 pm

I've got AC in 0.172 sec, I'd mistake in Tarjan's algorithm.
Giorgi Lekveishvili

Navid666
New poster
Posts: 7
Joined: Tue Jul 26, 2005 8:06 pm
Contact:

10510

Post by Navid666 » Wed Jul 12, 2006 9:34 pm

my code seems to be correct but still gettin WA
please give me some input/output... please !!!
thanks a lot...
=;GOOD LUCK=;
NAvidOP

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10510

Post by Martin Macko » Sun Jul 23, 2006 11:25 pm

Navid666 wrote:my code seems to be correct but still gettin WA
please give me some input/output... please !!!
thanks a lot...
If you post some test cases here, I can generate the correct outputs for you 8)

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Mar 24, 2007 6:22 pm

Hello..~

What is the correct output for this input..?

Code: Select all

1
4
4
0 1
1 0
2 3
3 2
Thanks.. :-)

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Jun 01, 2007 6:23 am

What is the correct output for this input..?

Code: Select all

1
4
4
0 1
1 0
2 3
3 2
NO

Is is not strongly connected.

Post Reply

Return to “Volume 105 (10500-10599)”