## 10510 - Cactus

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10510 - Cactus

What is the O(n) algorithm for strongly connected components?

I just thought you can find the reverse dfs for a node, and the regular dfs for a node, and if they both reach everyone, then there's one component.. but I get WA..

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

### Re: 10510 O(n)?

Larry wrote:What is the O(n) algorithm for strongly connected components?

I just thought you can find the reverse dfs for a node, and the regular dfs for a node, and if they both reach everyone, then there's one component.. but I get WA..
Yes, that is enough to determine if a graph is strongly connected. Assuming by "reverse DFS" you mean DFS with the arcs reversed.

How are you checking the second requirement, that each edge is in only one cycle?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
My method is to find all strong connect compoents
For each node of every strong connect compoents, I calculate every nodes' in-degree and out-degree belongs to the strong connect compoent
,and check if in-degrees are equal to out-degrees
if true , puts yes lese puts no
Could someone tell me if I am right?
Or give me some input/output

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
Try this input:

1
4
8
0 1
1 2
2 3
3 0
2 4
4 2
3 4
4 3

This is not cactus, but for every node in-degree equals to out-degree.
Am I right?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Alexander Kozlov wrote:Try this input:

This is not cactus, but for every node in-degree equals to out-degree.
Am I right?
I have already know my method is wrong.
How do you solve the problem?

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
Unfortunately I have not solved this problem yet and have no idea how to sove it.

mark00lui
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:
Alexander Kozlov wrote:Try this input:

1
4
8
0 1
1 2
2 3
3 0
2 4
4 2
3 4
4 3

This is not cactus, but for every node in-degree equals to out-degree.
Am I right?
is that we can slove in biconnective algorithm?
biconnective can be to find the SCC and back/forward/tree edges

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:

### 10510Cactus

Is this Kernel DAG ?? [/url]
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

Bilash
New poster
Posts: 3
Joined: Sat Oct 04, 2003 8:55 pm
Contact:
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
Can anybody tell me the correct approach to solving this problem?
Treat me like an angel and I will take you to heaven

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:
I thing the second part of this problem is the main fact as

1)We can compute in E time (E is the number of edge) where is the graph is Strongly connected. Such as Kosaraju's algorithms, Tarjan Algorithms and Gabow's algorithms is enough.

2)If the algo return 1 then it's strongly connected becaz there is only one tree.

But i cannot understand i,e. how can i handel the second part of the problem. Must be some triky way can anybody give some hints about this.

May be some to track when we use the revers DFS in Tarjan or other algorithms but i did not find this.
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
I've successfully solved it by modified DFS. It's something like Tarjan's algorithm for strongly connected components. But, moreove, we check for forward and cross edges in DFS tree (if there are any, given graph is not a cactus). Then we check for a situation, where the edge, that led us to current node lies in 2 cycles. That is iff there are two or more edges from current node's subtree to one of the nodes "above" current node.

And don't forget on special cases (like disconnected graph, n==1, etc.)

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.

Bilash
New poster
Posts: 3
Joined: Sat Oct 04, 2003 8:55 pm
Contact:
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).
Treat me like an angel and I will take you to heaven

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:
Ya i got the AC ))
I use the Gabow's Algo in O(m) time to calculate the Strongly connectivity and in this algo i track the cross edge and forward edge. And count same thing as Bilash done for the back edge.

I mind this is a great problem to know the Anatomy of DFS tree.

I am not satisfied with the memory. I use 2076. But some of the people done it in only 64.But how is it possible. Can anybody help about this point.
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm
I did what the 3 rules say...but I still get WA
Can anyone please give some special case??
I have tried some cases and the answers seem correct...
Thank you very much

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
Oh...., I also got WA. My algo. is very simple: From an arbitrary vertice, use DFS to reach the next vertice, if the current reached vertice has been visited, that means a cycle has been found, then set all of the edges on the cycle to be used, and return, if one of the edges has been set to be used, then this graphics is not a cactus.
Here is my code: Could anybody point out where my bug is?
Thanks very much!!!
[cpp]
set<int> con[10010];
map<int, map<int, bool> > used; // denote whether the edge connect from i to j is valid
bool visited[10010]; // denote whether a vertice has been visited
int pre[10010];
int n, m;

bool go(int id, int last) {
if ( visited[id] ) {
// find a cycle, set all of the edges on the cycle to be used.
// if one of the edge has been set to be used, then return false
int cur = id;
int p = last;
while ( true ) {
if ( used[p][cur] )
used[p][cur] = false;
else
return false;
if ( p==id ) break;
cur = p;
p = pre[cur];
}
return true;
} else {
// if this vertice has no out-edge, then the graphics cannot be a cactus
if ( con[id].empty() ) return false;
visited[id] = true;
pre[id] = last;
for(set<int>::iterator it = con[id].begin(); it != con[id].end(); it ++) {
if ( !go(*it, id) ) return false;
}
return true;
}
}
void main()
{
int t;
fin >> t;
for(int T = 0;T < t;T ++) {
fin >> n >> m;
for(int i = 0;i < n;i ++) {
con.clear();
pre = -1;
}
used.clear();
memset(visited, false, sizeof(visited));
for(int i = 0;i < m;i ++) {
int s, t;
fin >> s >> t;
con[s].insert(t);
used[s][t] = true;
}
if ( !n )
cout << "NO" << endl;
else if ( !m )
cout << "NO" << endl;
else {
if ( !go(0, -1) )
cout << "NO" << endl;
else {
for(int i = 0;i < n;i ++)
if ( !visited ) {
cout << "NO" << endl;
goto loop;
}
cout << "YES" << endl;
}
}
loop: ;
}
}
[/cpp]