Rate flow on chart

Question

Given an undirected graph, all edges have a weight of 1; N, M are about 10 6 I need to find out if there is more flow between the source and the receiver than some value of X. X is quite small.

Using bfs until the stream is equal to X gives O (M * X), ​​this is too slow for me.

Is there a faster flow estimation method?

Answer 1

what you need is basically maxflow, see http://en.wikipedia.org/wiki/Maximum_flow_problem

and the dinic algorithm is recommended for practical use.

and in case you need some kind of example, you can refer to one of my codes, http://wiki.attiix.com/index.php?title=Maxflow