0
$\begingroup$

In a directed graph, if you find scc (strongly connected components), then for each negative edge, if its 2 vertices are in the same scc and that scc has size > 1, then there is a negative cycle with that edge, and is easy to find it with a simple dfs. Is this approach correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

No it's not true. Consider a graph with two nodes, A and B, with an edge A->B with length 1 and an edge B->A with length -1.

The edge B->A is a negative edge and its vertices are in the same SCC and that SCC has size > 1. That edge is not part of a negative cycle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, right. Thanks $\endgroup$
    – Lorenzo Tinfena
    Commented Mar 4 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.