### Moody_Nabil's blog

By Moody_Nabil, history, 6 weeks 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<=105,n−1<=m<=7∗105

You can find the problem here. It will be really helpful if you can provide me with a solution.

• -5

 » 6 weeks ago, # | ← Rev. 2 →   0 A pair $(u,v)$ should be counted when $u$ and $v$ are in the same 2-edge-connected component, but not in the same 3-edge-connected component. (This is Menger's theorem.) So you can find the 2- and 3-edge-connected components, and then it's an easy combinatorics problem to extract the answer from their sizes.Finding 2-edge-connected components is well-known to be possible with little more than normal DFS and is also called bridge-finding. There are many resources available on this topic. See, for example, this blog for details. There are also fast algorithms for finding 3-edge-connected components in the literature but these aren't as widely known and I'm not personally familiar with them.
•  » » 6 weeks ago, # ^ |   0 Fun fact: you can find all k-edge-conntected components with the help of Gomory-Hu tree — refer to this paper for more info: https://www.researchgate.net/publication/281778259_A_Simple_Algorithm_for_Finding_All_k-Edge-Connected_Components#pf9.For this problem, though, I guess you could create any spanning tree and do some DP counting all pairs of vertices that are connected by more than one returning edge? Just an idea. Anyway, finding 3-CCs sounds like a bit of an overkill to me.
•  » » 6 weeks ago, # ^ |   0 Thanks alot