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

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 3

Input: 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 set
int 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 union
void 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 Code
int 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 approach
import java.util.*;
class GFG{
 
// Function to perform the find operation
// to find the parent of a disjoint set
static 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 union
static 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 Code
public 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 set
def 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 union
def 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 Code
if __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 approach
using System;
 
public class GFG{
 
// Function to perform the find operation
// to find the parent of a disjoint set
static 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 union
static 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 Code
public 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 set
function Find(parent, a) {
  return (parent[a] = parent[a] == a ? a : Find(parent, parent[a]));
}
 
// FUnction to perform union operation
// of disjoint set union
function 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 Code
 
let 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)


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
Implementation of Johnson’s algorithm for all-pairs shortest paths Implementation of Johnson’s algorithm for all-pairs shortest paths
Smallest vertex in the connected components of all the vertices in given undirect graph Smallest vertex in the connected components of all the vertices in given undirect graph
Minimum number of edges to be removed from given Graph such that no path exists between given pairs of vertices Minimum number of edges to be removed from given Graph such that no path exists between given pairs of vertices
Minimum length paths between 1 to N including each node Minimum length paths between 1 to N including each node
Find if possible to visit every nodes in given Graph exactly once based on given conditions Find if possible to visit every nodes in given Graph exactly once based on given conditions

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje