Maximum element in the connected component of the given node for Q queries

Efficient Approach

Now let’s see if we can figure out any better approach. One thing to notice in this question is that the answer will be the same for every element of a connected component (equal to the maximum element in the connected component). Therefore, we can combine the nodes of a component into a single group. This can be done using Disjoint Set Union. 

Initially, all the elements form different disjoint sets. Now we iterate over ‘arr’ and perform the DSU union operation on the elements of the given edge and simultaneously maintain the ‘maxElement’ for each set. After creating the data structure, for each query, perform a find operation to get the parent ‘currentParent’ of that set, and ‘maxElement[currentParent]’ will be the required answer.

Algorithm

• Create 3 vectors - ‘parent’, ‘rank’, ‘maxElement’.
• Initialize ‘parent[i]’=i and ‘maxElement[i]’=i for 1<=i<=N.
• Iterate over the array and perform union operation of ‘arr[i].first’, ‘arr[i].second’.
• Now for every query:
  • Find parent of the node ‘queries[i]’.
  • Output the value of ‘maxElement[currentParent]’.

C++ Code

#include<bits/stdc++.h> using namespace std; // Function to find root of the disjoint set int Find(vector<int>& parent, int node) { if (parent[node] == node){ return parent[node]; } else{ parent[node] = Find(parent, parent[node]); return parent[node]; } } // Function to perform DSU union operation void Union(int u, int v, vector<int>& parent, vector<int>& rank, vector<int>& maxElement){ u = Find(parent, u); v = Find(parent, v); // if both elements are already in the same set if (u == v) return; // If the ranks are the same if (rank[u] == rank[v]) { rank[u]++; } // if the rank of u is less, swap u and v if (rank[u] < rank[v]) { swap(u,v);    } // Updating parent of v parent[v] = u; // Updating maxElement maxElement[u] = max(maxElement[u], maxElement[v]); } void solve(int N, int M, int Q, vector<pair<int,int>>& arr, vector<int> &queries){ // Vector to store the parent of a node vector<int> parent(N + 1); // Vector to store rank of a node for DSU vector<int> rank(N + 1, 0); // Vector to store maximum element of a set vector<int> maxElement(N + 1); // Initializing vectors for(int i=0; i<=N; i++){ parent[i] = i; maxElement[i] = i; } // Iterating over arr and performing union operation for (int i = 0; i < M; i++) { Union(arr[i].first, arr[i].second, parent, rank, maxElement); } // Iterating over queries for (int i = 0; i < Q; i++){ // Finding parent of the given node int currentParent = Find(parent, queries[i]); // Printing max element of the set cout<<maxElement[currentParent]<<" "; } cout<<endl; } // Driver Code int main(){ int N = 5; vector<pair<int,int>>arr { {1,2}, {2,4}, {3,5} }; vector<int> queries{ 3, 2, 4 }; int M = arr.size(); int Q = queries.size(); solve(N, M, Q, arr, queries); return 0; } You can also try this code with Online C++ Compiler Run Code

Output:

5 4 4

You can also try this code with Online C++ Compiler

Run Code

Time Complexity:

We have implemented the following functions to implement DSU:

find(): This will take O(logN) time in the worst case for a single call.

union(): This function calls find() two times. Other operations take constant time. So overall complexity is O(logN) for a single call.

Union operation is performed once for each edge, so the total time complexity of creating DSU is O(MlogN). Further, there are Q queries and for each query, the find operation is performed once. Therefore the time complexity for answering the queries in O(QlogN).

Total Time Complexity: max(MlogN, QlogN).

Space Complexity: 

We have created 3 new vectors of length O(N) for creating DSU and answering queries. 

Total Space Complexity: O(N).

FAQs

1. What is a Disjoint Set data structure?
   A disjoint set data structure allows us to keep track of a set of elements partitioned into disjoint sets. We can add new sets, merge two sets, and find parent of a set using this data structure.
    
2. Explain Find operation on Disjoint Set data structure.
   The Find operation is performed by following the parent pointers from the given node until we reach the root element.
    
3. Explain union operation on DSU?
   Union of two nodes ‘x’ and ‘y’ replaces the set containing ‘x’ and the set containing ‘y’ with their union. First, we use two Find operations to get the roots of the sets containing ‘x’ and ‘y’. If both the roots are the same, we have to do nothing, else merge both sets by either setting parent of ‘x’ to ‘y’ or by setting parent of ‘y’ to ‘x’.

Key Takeaways

In this article, we discussed how to find the maximum element in the connected component of a node for Q queries. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.