![:(](./images/smilies/icon_frown.gif)
Thanx!
Moderator: Board moderators
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.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![]()
Can anybody tell me the correct approach to solving this problem?
horape wrote: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.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![]()
Can anybody tell me the correct approach to solving this problem?
Saludos,
HoraPe
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)junbin wrote:I'm not very good at graph theory... what do you mean by cross/forward edge?horape wrote: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)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![]()
Can anybody tell me the correct approach to solving this problem?
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 incorrectExaminer 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
I don't think this is correct. This condition is necessary but not sufficient for a directed graph to be a cactus: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.
Code: Select all
1
3
6
0 1
1 0
1 2
2 1
2 0
0 2
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).
Code: Select all
1
4
5
0 1
1 2
2 1
2 3
3 0
If you post some test cases here, I can generate the correct outputs for youNavid666 wrote:my code seems to be correct but still gettin WA
please give me some input/output... please !!!
thanks a lot...
Code: Select all
1
4
4
0 1
1 0
2 3
3 2
Code: Select all
1
4
4
0 1
1 0
2 3
3 2