10510 - Cactus

[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..

[Lars Hellsten]

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]

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

[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?

[windows2k]

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?

[Alexander Kozlov]

Unfortunately I have not solved this problem yet and have no idea how to sove it.

[mark00lui]

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]

Is this Kernel DAG ?? [/url]

[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
Can anybody tell me the correct approach to solving this problem?

[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.

[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.

[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).

[Grinder]

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.

[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

[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]