Solution 3 for Scaler Topics Fortnightly Contest - 5

This article is part of the Scaler Topics Fortnightly Contest - 5.

Solution Approach

• Given a graph with A nodes and M edges. We have to process two types of queries.

1. Remove an edge between X and Y.
2. Return the maximum sum out of all the connected componenets.

• If we reverse our queries, our first query changes from removing an edge to adding an edge.
• Now, we have to think of a data structure which support two types of operations - Union and Get.
• We can perform this using Disjoint Set Union (DSU). Although, the implementation should be in a way such that both the operations are of O(log N) time complexity.

The steps are as follows:

1. Generate a hash for all the edges in the array C. (Hash should be generated such that querying for (b, a) should also give positive if (a, b) is present).
2. Delete all the edges present in array D.
3. Perform the query operations in reverse order.
4. Lastly, again reverse the answers stored and return the array.

C++ Implementation

Java Implementation

Python Implementation