Блог пользователя FrozenBlood

A Problem on Perfect Matching
Автор FrozenBlood, история, 5 лет назад, По-английски

You will be given a bipartite graph, each side have N nodes where N<=10^5. There will be M<=10^5 edges between these nodes. It is guranteed that the initial graph is given in such a way that the graph has exactly N matching. How many edges are there if I remove one of them the matching of the graph will be less than N? Here is the problem https://open.kattis.com/problems/justenoughbridges.

Any idea?

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by FrozenBlood (previous revision, new revision, compare).

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Not sure, but the idea is:

  1. Lets count $$$m - answer$$$, i.e. the number of edges that break the perfect matching if removed
  2. Solve for each component separately.
  3. If the vertex has only one edge, the edge obviously breaks the perfect matching, add it to answer and remove both vertices of it (and all corresponding edges), repeat
  4. Now any vertex has at least 2 edges and there's a perfect matching and also the component is connected, looks like (can't stricktly prove this) for the component of size $$$V$$$ we can build a cycle of length $$$2V$$$ containing the perfect matching, so we can replace the edges from perfect matching to ones between them in the path, so none of them are in the answer
→ Ответить