PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bridges in Graph, Online bridge queries
PROBLEM:
We are given an undirected graph with n vertices and m edges. Initially the graph contains only the vertices and no edges. For each of the m edges given, we add each edge to the graph and then immediately report the current number of bridges in the graph.
EXPLANATION:
We are given an undirected graph as input and we have to find the bridges in the graph after each edge was added to the graph.
So, it might seem like we can add each edge to the graph and then apply Tarjan’s algorithm to find the number of bridges in the graph at that point . But the time complexity of Tarjan’ s algorithm is O(n+m) and we will have to apply this for m times (once after adding each edge to the graph). So the overall complexity will be O(nm + m2) which will timeout in this case.
So we need something better. It turns out that we can use disjoint set to perform this task efficiently. Below is a link which describes exactly how to find the bridges online in a graph with the implementation details. The algorithm described there works in O(n log(n) + m log(n)) time which is feasible for the constraints given in the problem. The implementation uses path compression only and not union by rank. Applying union by rank can reduce the time complexity further to O(n log(n) + m).
Link
After adding each edge in the graph, we need to print the number of bridges in the graph currently at that point.
See solution for clarity.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.