Page 1 of 3

10510 - Cactus

Posted: Sat Jun 28, 2003 3:14 pm
by Larry
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..

thanks in advance..

Re: 10510 O(n)?

Posted: Tue Jul 01, 2003 4:53 am
by Lars Hellsten
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?

Posted: Wed Jul 02, 2003 6:38 am
by windows2k
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
Thx in advance

Posted: Wed Jul 02, 2003 10:51 am
by Alexander Kozlov
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?

Posted: Wed Jul 02, 2003 12:22 pm
by windows2k
Alexander Kozlov wrote:Try this input:

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

Posted: Wed Jul 02, 2003 2:30 pm
by Alexander Kozlov
Unfortunately I have not solved this problem yet and have no idea how to sove it. :(

Posted: Tue Jul 29, 2003 5:42 am
by mark00lui
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

10510Cactus

Posted: Fri Oct 17, 2003 4:27 pm
by Grinder
Is this Kernel DAG ?? :o [/url]

Posted: Fri Oct 17, 2003 11:25 pm
by Bilash
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?

Posted: Sat Oct 18, 2003 12:36 pm
by Grinder
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.
:o

Posted: Sat Oct 18, 2003 11:03 pm
by marian
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.

Posted: Tue Oct 21, 2003 9:31 pm
by Bilash
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).

Posted: Wed Oct 22, 2003 2:48 pm
by Grinder
Ya i got the AC :D )) :)
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. :roll:

Posted: Wed Nov 26, 2003 6:03 pm
by cplusplus
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 :)

Posted: Thu Nov 27, 2003 1:44 pm
by Tomson
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]