PROBLEM LINK:
Author: Kush Khandelwal
Tester: Vivek Bansal
Editorialist: Kush Khandelwal
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Bridge Tree, LCA
PROBLEM:
A graph has n vertices and m edges in which only bridge edges contain unit weight while all the other edges have zero weight.
For every query, you have to output the minimum sum of weights of edges in which you can travel from city A to city B.
EXPLANATION:
Since only bridge edges contain unit weight, we make a tree of a given graph in which the tree contains only those edges which were bridges in the original graph.
For those who do not know about how to make a bridge tree of a given graph, kindly go through this link.
It has a very clear explanation with a working code for the same.
After we create the bridge tree of the given graph, for every query, we find the connected component in
which the both vertices lie.
If they lie in the same component naturally the answer is zero, otherwise output the minimum path between two vertices in a tree which is a fairly easy problem and can easily be solved with the help of LCA on trees.