Simple Cycles - Codeforces

5 лет назад, # |

← Rev. 2 →

I think that you can run a linear-time bridge finding algo. If there is at least one edge that is not a bridge, then you have a simple cycle. This works because, if you consider the DFS spanning tree and gradually add more edges to it, if an edge is not an bridge, that means that there is a path from a child node to nodes that are visited earlier or same time as its ancestors.

Edit This answer is incorrect because I missed the fact that the cycle must contain both s and t.

→ Ответить

5 лет назад, # ^ |

this finds a simple cycle but not necessary one that contains $$$s$$$ or $$$t$$$

→ Ответить

5 лет назад, # ^ |

Ah yes. I missed that fact. Sorry.

→ Ответить

5 лет назад, # |

← Rev. 4 →

2 The best that I can think of is a quadratic time algorithm. Run MST algorithm. Then try adding an arbitrary edge to the MST. There will be a cycle for sure. Now, you can use DFS to check the weight of this cycle. Do this for every edge.

Edit This answer is incorrect because I missed the fact that the cycle must contain both s and t.

→ Ответить

5 лет назад, # ^ |

← Rev. 5 →

This does not work. A minimum cycle can need more than one edge which is not in the MST. example graph:

s = 0, t = 1
(0, 1) w = 4
(1, 2) w = 4
(2, 3) w = 4
(4, 5) w = 4
(5, 0) w = 4
(1, 3) w = 5
(3, 4) w = 5
(4, 0) w = 4

→ Ответить

5 лет назад, # ^ |

← Rev. 3 →

I missed the point that the cycle must contain s and t so my answer is incorrect for your counterexample.

On a side note, I believe it should be correct if we remove that restriction (and assume non-negative weights). Because there is no way we can add more than 1 edge to the MST to create a minimum cycle unless there are negative weights.

→ Ответить

5 лет назад, # ^ |

← Rev. 5 →

that should be right, yes. I believe with negative weights this becomes NP hard and it can be reduced to a hamilton cicle problem (just set every weight to $$$-1$$$, than there is a hamilton circle iff the weight of the minimal circle is $$$-n$$$).

→ Ответить

5 лет назад, # |

← Rev. 4 →

+25

For problem one we can use Menger's theorem which tells us that there are two vertex disjoint path (those form a simply cycle) between $$$s$$$ and $$$t$$$ iff there is no single vertex which seperates them. This is equivalent to they are in the same biconnected component (vertex connectivity) which can be found in $$$\mathcal{O}(n)$$$. Then those two paths can be found with a bfs.

problem two with negative weights is NP hard... best Solution for problem two with positive weights i can think of right now is to use a min cost max flow based approch...

→ Ответить

HalfFragment

5 лет назад, # ^ |

← Rev. 2 →

"This is equivalent to they are in the same biconnected component (vertex connectivity) which can be found in O(n)."

May you suggest how i can find a biconnected component consist of vertex s and t.

→ Ответить

5 лет назад, # ^ |

I think you can just compute biconnected components of the graph (there are well-known algorithms that you can find online). Then check if s and t are in the same biconnected component.

→ Ответить

5 лет назад, # ^ |

← Rev. 3 →

Can't you just find two vertex-disjoint paths with two dfs ?

The first dfs starts from s and ends to t and finds a path.

The second dfs starts from s and ends to t but uses only vertices that first path did not use.

The union of these paths is the cycle you need. Isn't that right and simpler ?

→ Ответить

HalfFragment

5 лет назад, # ^ |

Here Again, This will be counterexample
(1, 2) weight = 1
(2, 4) weight = 100
(1, 3) weight = 100
(3, 4) weight = 1
(2, 3) weight = 1
where (x, y) represent edge;
and s = 1, t = 4,
what if first dfs find path 1-2-3-4??

→ Ответить

5 лет назад, # ^ |

Opps, I am sorry. Max-flow is used for vertex-disjoint paths. It's not linear though as you want. My bad !

→ Ответить

https://en.wikipedia.org/wiki/Suurballe%27s_algorithm ?

5 лет назад, # ^ |

Maybe we could use max-flow algorithm in linear time though, because we just need to iterate the graph twice only. So what if you build a new graph with the "back" edges as well and run the max flow algorithm twice ?

→ Ответить

arknave

5 лет назад, # ^ |

→ Ответить