Given an array of pairs arr[][] of length N, and an array queries[] of length M, and an integer R, where queries[i] contain an integer from 1 to R, the task for every queries[i] is to find the maximum element of the connected components of the node with value queries[i].
Note: Initially every integer from 1 to R belongs to the distinct set.
Examples:
Input: R = 5, arr = {{1, 2}, {2, 3}, {4, 5}}, queries[] = {2, 4, 1, 3}
Output: 3 5 3 3
Explanation: After making the sets from the arr[] pairs, {1, 2, 3}, {4, 5}
For the first query: 2 belongs to the set {1, 2, 3} and the maximum element is 3
For the second query: 4 belongs to the set {4, 5} and the maximum element is 5
For the third query: 1 belongs to the set {1, 2, 3} and the maximum element is 3
For the fourth query: 3 belongs to the set {1, 2, 3} and the maximum element is 3Input: R = 6, arr = {{1, 3}, {2, 4}}, queries = {2, 5, 6, 1}
Output: 4 5 6 3
Approach: The given problem can be solved using the Disjoint Set Union. Initially, all the elements are in different sets, process the arr[] and do union operation on the given pairs and in union update, the maximum value for each set in the array, say maxValue[] value for the parent element. For each query perform the find operation and for the returned parent element find the maxParent[parent]. Follow the steps below to solve the problem:
- Initialize a vector maxValue[] to find the maximum element of every set.
- Initialize the vectors parent(R+1), rank(R+1, 0), maxValue(R+1).
- Iterate over the range [1, R+1) using the variable i and set the value of parent[i] and maxValue[i] as i.
- Iterate over the range [1, N-1] using the variable i and call for function operation Union(parent, rank, maxValue, arr[i].first, arr[i].second).
- Iterate over the range [1, M-1] using the variable i and perform the following steps:
- call for function operation Find(parent, queries[i]).
- Print the value of maxValue[i] as the resultant maximum element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the find operation// to find the parent of a disjoint setint Find(vector<int>& parent, int a){ return parent[a] = (parent[a] == a) ? a : (Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionvoid Union(vector<int>& parent, vector<int>& rank, vector<int>& maxValue, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (a == b) return; // If the rank are the same if (rank[a] == rank[b]) { rank[a]++; } if (rank[a] < rank[b]) { int temp = a; a = b; b = temp; } parent[b] = a; // Update the maximum value maxValue[a] = max(maxValue[a], maxValue[b]);}// Function to find the maximum element// of the set which belongs to the// element queries[i]void findMaxValueOfSet( vector<pair<int, int> >& arr, vector<int>& queries, int R, int N, int M){ // Stores the parent elements // of the sets vector<int> parent(R + 1); // Stores the rank of the sets vector<int> rank(R + 1, 0); // Stores the maxValue of the sets vector<int> maxValue(R + 1); for (int i = 1; i < R + 1; i++) { // Update parent[i] and // maxValue[i] to i parent[i] = maxValue[i] = i; } for (int i = 0; i < N; i++) { // Add arr[i].first and // arr[i].second elements to // the same set Union(parent, rank, maxValue, arr[i].first, arr[i].second); } for (int i = 0; i < M; i++) { // Find the parent element of // the element queries[i] int P = Find(parent, queries[i]); // Print the maximum value // of the set which belongs // to the element P cout << maxValue[P] << " "; }}// Driver Codeint main(){ int R = 5; vector<pair<int, int> > arr{ { 1, 2 }, { 2, 3 }, { 4, 5 } }; vector<int> queries{ 2, 4, 1, 3 }; int N = arr.size(); int M = queries.size(); findMaxValueOfSet(arr, queries, R, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to perform the find operation// to find the parent of a disjoint setstatic int Find(int [] parent, int a){ return parent[a] = (parent[a] == a) ? a : (Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionstatic void Union(int [] parent, int [] rank, int [] maxValue, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (a == b) return; // If the rank are the same if (rank[a] == rank[b]) { rank[a]++; } if (rank[a] < rank[b]) { int temp = a; a = b; b = temp; } parent[b] = a; // Update the maximum value maxValue[a] = Math.max(maxValue[a], maxValue[b]);}// Function to find the maximum element// of the set which belongs to the// element queries[i]static void findMaxValueOfSet( int[][] arr, int [] queries, int R, int N, int M){ // Stores the parent elements // of the sets int [] parent = new int[R + 1]; // Stores the rank of the sets int [] rank = new int[R + 1]; // Stores the maxValue of the sets int [] maxValue = new int[R + 1]; for (int i = 1; i < R + 1; i++) { // Update parent[i] and // maxValue[i] to i parent[i] = maxValue[i] = i; } for (int i = 0; i < N; i++) { // Add arr[i][0] and // arr[i][1] elements to // the same set Union(parent, rank, maxValue, arr[i][0], arr[i][1]); } for (int i = 0; i < M; i++) { // Find the parent element of // the element queries[i] int P = Find(parent, queries[i]); // Print the maximum value // of the set which belongs // to the element P System.out.print(maxValue[P]+ " "); }}// Driver Codepublic static void main(String[] args){ int R = 5; int[][] arr ={ { 1, 2 }, { 2, 3 }, { 4, 5 } }; int [] queries = { 2, 4, 1, 3 }; int N = arr.length; int M = queries.length; findMaxValueOfSet(arr, queries, R, N, M);}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approach# Function to perform the find operation# to find the parent of a disjoint setdef Find(parent, a): if(parent[parent[a]]!=parent[a]): parent[a]=findParent(parent,parent[a]) return parent[a] #return parent[a] = a if (parent[a] == a) else Find(parent, parent[a])# FUnction to perform union operation# of disjoint set uniondef Union(parent, rank, maxValue, a, b): a = Find(parent, a) b = Find(parent, b) if (a == b): return # If the rank are the same if (rank[a] == rank[b]): rank[a] += 1 if (rank[a] < rank[b]): temp = a a = b b = temp parent[b] = a # Update the maximum value maxValue[a] = max(maxValue[a],maxValue[b])# Function to find the maximum element# of the set which belongs to the# element queries[i]def findMaxValueOfSet(arr,queries, R, N, M): # Stores the parent elements # of the sets parent = [1 for i in range(R+1)] # Stores the rank of the sets rank = [0 for i in range(R+1)] # Stores the maxValue of the sets maxValue = [0 for i in range(R + 1)] for i in range(1,R + 1,1): # Update parent[i] and # maxValue[i] to i parent[i] = maxValue[i] = i for i in range(N): # Add arr[i].first and # arr[i].second elements to # the same set Union(parent, rank, maxValue, arr[i][0],arr[i][1]) for i in range(M): # Find the parent element of # the element queries[i] P = Find(parent, queries[i]) # Print the maximum value # of the set which belongs # to the element P print(maxValue[P],end = " ")# Driver Codeif __name__ == '__main__': R = 5 arr = [[1, 2], [2, 3], [4, 5]]; queries = [2, 4, 1, 3] N = len(arr) M = len(queries) findMaxValueOfSet(arr, queries, R, N, M) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{// Function to perform the find operation// to find the parent of a disjoint setstatic int Find(int [] parent, int a){ return parent[a] = (parent[a] == a) ? a : (Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionstatic void Union(int [] parent, int [] rank, int [] maxValue, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (a == b) return; // If the rank are the same if (rank[a] == rank[b]) { rank[a]++; } if (rank[a] < rank[b]) { int temp = a; a = b; b = temp; } parent[b] = a; // Update the maximum value maxValue[a] = Math.Max(maxValue[a], maxValue[b]);}// Function to find the maximum element// of the set which belongs to the// element queries[i]static void findMaxValueOfSet( int[,] arr, int [] queries, int R, int N, int M){ // Stores the parent elements // of the sets int [] parent = new int[R + 1]; // Stores the rank of the sets int [] rank = new int[R + 1]; // Stores the maxValue of the sets int [] maxValue = new int[R + 1]; for (int i = 1; i < R + 1; i++) { // Update parent[i] and // maxValue[i] to i parent[i] = maxValue[i] = i; } for (int i = 0; i < N; i++) { // Add arr[i,0] and // arr[i,1] elements to // the same set Union(parent, rank, maxValue, arr[i,0], arr[i,1]); } for (int i = 0; i < M; i++) { // Find the parent element of // the element queries[i] int P = Find(parent, queries[i]); // Print the maximum value // of the set which belongs // to the element P Console.Write(maxValue[P]+ " "); }}// Driver Codepublic static void Main(String[] args){ int R = 5; int[,] arr ={ { 1, 2 }, { 2, 3 }, { 4, 5 } }; int [] queries = { 2, 4, 1, 3 }; int N = arr.GetLength(0); int M = queries.Length; findMaxValueOfSet(arr, queries, R, N, M);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to perform the find operation// to find the parent of a disjoint setfunction Find(parent, a) { return (parent[a] = parent[a] == a ? a : Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionfunction Union(parent, rank, maxValue, a, b) { a = Find(parent, a); b = Find(parent, b); if (a == b) return; // If the rank are the same if (rank[a] == rank[b]) { rank[a]++; } if (rank[a] < rank[b]) { let temp = a; a = b; b = temp; } parent[b] = a; // Update the maximum value maxValue[a] = Math.max(maxValue[a], maxValue[b]);}// Function to find the maximum element// of the set which belongs to the// element queries[i]function findMaxValueOfSet(arr, queries, R, N, M) { // Stores the parent elements // of the sets let parent = new Array(R + 1); // Stores the rank of the sets let rank = new Array(R + 1).fill(0); // Stores the maxValue of the sets let maxValue = new Array(R + 1); for (let i = 1; i < R + 1; i++) { // Update parent[i] and // maxValue[i] to i parent[i] = maxValue[i] = i; } for (let i = 0; i < N; i++) { // Add arr[i][0] and // arr[i][1] elements to // the same set Union(parent, rank, maxValue, arr[i][0], arr[i][1]); } for (let i = 0; i < M; i++) { // Find the parent element of // the element queries[i] let P = Find(parent, queries[i]); // Print the maximum value // of the set which belongs // to the element P document.write(maxValue[P] + " "); }}// Driver Codelet R = 5;let arr = [ [1, 2], [2, 3], [4, 5],];let queries = [2, 4, 1, 3];let N = arr.length;let M = queries.length;findMaxValueOfSet(arr, queries, R, N, M);// This code is contributed by ipg2016107</script> |
Output:
3 5 3 3
Time Complexity: O(N*log M)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!