A Problem on Perfect Matching
Difference between en1 and en2, changed 13 character(s)
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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English FrozenBlood 2019-11-07 10:33:25 13 Tiny change: 'ghbridges.' -> 'ghbridges.\n\nAny idea?'
en1 English FrozenBlood 2019-11-07 09:21:16 422 Initial revision (published)