An Interesting Problem On MaxFlow. Can You Solve It?

Revision en2, by Moody_Nabil, 2021-10-19 19:52:01

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Moody_Nabil 2021-10-19 19:52:01 2 Tiny change: 'm<=7∗105\nYou can ' -> 'm<=7∗105\n\nYou can '
en1 English Moody_Nabil 2021-10-19 19:51:36 587 Initial revision (published)