Solution 3 for Scaler Topics Fortnightly Contest - 5

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

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

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

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation