FrozenBlood's blog

A Problem on Perfect Matching
By FrozenBlood, history, 5 years ago, In English

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?

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Finding SSC on the residual graph will be enough. If a edge in a SSC then it is deletable.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you get the residual graph for $$$N, M \leq 10^5$$$?

      → Reply