PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Given an undirected graph, find number of pairs of vertices such that there are at least two edge disjoint paths between them.
QUICK EXPLANATION:
The two vertices should belong to the same component in the bridge tree of graph
EXPLANATION:
What does it mean to have two edge disjoint paths between two vertices?
Even if we remove one of the edges on the path, because of the other path, the graph ( not only the two vertices ) remain connected. Those edges are not bridges.
Bridges are the edges whose removal disconnects the graph.
How do we check if the two vertices are connected by path without any bridges or not ?
If we remove the bridges in the graph, the graph is broken into several components. Even if we remove some edge in the component, the component is still connected as that edge is not a bridge. Thus, we get something like a tree. We should check that after removing bridges in the graph, whether these two vertices are in the same component or not. Please refer to this excellent tutorial on bridge tree.
Now all that remains is to find out which edges of the graph are bridges. First, we can do a single dfs to construct dfs tree of the graph. The edges not in dfs tree cannot be bridges. We can do a dp on the tree dfs to find out bridge edges. First, root the tree at an arbitrary vertex. Do dfs and calculate the level(= distance from root) of every vertex. We calculate the minimum level that can be reached by edges from vertices in the subgraph rooted at every vertex.
AUTHOR’S SOLUTION:
Author’s solution can be found here.
Tester’s solution can be found here.