I am stuck on this following problem for a pretty long time.
Given a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges and the capacity of each edge is $$$1$$$. $$$maxFlow(u, v)$$$ defines the maximum flow from node $$$u$$$ to node $$$v$$$. You have to find out how many pair of nodes $$$(u, v)$$$ are there where $$$u < v$$$ and $$$maxFlow(u, v) = 2$$$ .You can assume that the graph won’t have any self loop.
$$$Constraints: 1<=n<=10^5, n-1<=m<=7*10^5$$$
You can find the problem here. It will be really helpful if you can provide me with a solution.
Hint: you need to find biconnected (2-edge connected) and triconnected (3-edge connected) components of graph (it can be done in linear time e.g. here pdf)
So if the whole graph is biconnected, what's the answer? Can't understand how this helps.
And the flow from one bi/triconnected comp. to another can also be 2.
1.Flow in triconnected components is at least 3 for every pair of vertices of this component.
2.Flow in biconnected components is at least 2 for every pair of vertices of this component.
3.Flow between two vertices of distinct biconnected components is 0 or 1.
So we need to count pairs of vertices which belong to the same biconnected component, but distinct triconnected components.
I don't think 3 holds. Let's say we have two cliques of size 3, who share a single vertex. Then that are two biconn. components right? But the flow from any vertex from one comp to any vertex in the other is 2, isn't it?
There are two 2-vertex connected components, but one 2-edge connected component in your graph. I said about later.
You can also view it in this (more obvious) way: find bridges and remove them, that takes care of flow 1. Then, find 3-edge-connected components and compress them into vertices. The flow between any two connected vertices is now 2. It can't be 3+, since if it was, these two vertices would be in a 3-edge-connected component.
There are no bridge, hence one biconnected (2-edge-connected) components.