### YouKn0wWho's blog

By YouKn0wWho, 9 months ago, ,

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.

• +54

 » 9 months ago, # | ← Rev. 5 →   +46 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)
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 9 months ago, # ^ | ← Rev. 5 →   +12 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.
•  » » » » 9 months ago, # ^ |   0 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?
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 There are two 2-vertex connected components, but one 2-edge connected component in your graph. I said about later.
•  » » » » » 9 months ago, # ^ |   +11 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.
•  » » » » » 9 months ago, # ^ |   +7 There are no bridge, hence one biconnected (2-edge-connected) components.