YouKn0wWho's blog

An Interesting Problem On MaxFlow. Can You Solve It?
By YouKn0wWho, 5 years ago, In English

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.

  • Vote: I like it
  • +54
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 5   Vote: I like it +46 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 5   Vote: I like it +12 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          There are two 2-vertex connected components, but one 2-edge connected component in your graph. I said about later.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          There are no bridge, hence one biconnected (2-edge-connected) components.

          → Reply