I have been trying to learn this algorithm from this https://www.hackerearth.com/practice/math/geometry/line-intersection-using-bentley-ottmann-algorithm/tutorial/. But there is no clear implementation. I have failed to implement it. Does anyone have a good implementation. It will be very helpful.

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?

This problem seems like a regular expression problem. If the constraints were small, it could be easily handled with dynamic programming I think. But it seems almost impossible with this kind of constraints. Any idea?