10510 - Cactus
Moderator: Board moderators
-
- 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..
thanks in advance..
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..
-
- New poster
- Posts: 20
- Joined: Thu Apr 10, 2003 10:53 pm
Re: 10510 O(n)?
Yes, that is enough to determine if a graph is strongly connected. Assuming by "reverse DFS" you mean DFS with the arcs reversed.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..
How are you checking the second requirement, that each edge is in only one cycle?
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
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
-
- New poster
- Posts: 23
- Joined: Sun Jun 15, 2003 4:45 pm
- Location: Ukraine
-
- New poster
- Posts: 23
- Joined: Sun Jun 15, 2003 4:45 pm
- Location: Ukraine
10510Cactus
Is this Kernel DAG ??
[/url]
![:o](./images/smilies/icon_eek.gif)
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.
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?
![:cry:](./images/smilies/icon_cry.gif)
Can anybody tell me the correct approach to solving this problem?
Treat me like an angel and I will take you to heaven
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](./images/smilies/icon_eek.gif)
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](./images/smilies/icon_eek.gif)
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.
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.
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.
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).
![:)](./images/smilies/icon_smile.gif)
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
Ya i got the AC
)) ![:)](./images/smilies/icon_smile.gif)
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:](./images/smilies/icon_rolleyes.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:)](./images/smilies/icon_smile.gif)
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:](./images/smilies/icon_rolleyes.gif)
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.
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]
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]