Dada una array de pares arr[][] de longitud N , y una array consultas[] de longitud M , y un número entero R , donde las consultas[i] contienen un número entero de 1 a R , la tarea para cada consulta[i] es encontrar el elemento máximo de los componentes conectados del Node con consultas de valor[i] .
Nota: Inicialmente, todo número entero de 1 a R pertenece al conjunto distinto.
Ejemplos:
Entrada: R = 5, arr = {{1, 2}, {2, 3}, {4, 5}}, queries[] = {2, 4, 1, 3}
Salida: 3 5 3 3
Explicación: Después haciendo los conjuntos a partir de los pares arr[], {1, 2, 3}, {4, 5}
Para la primera consulta: 2 pertenece al conjunto {1, 2, 3} y el elemento máximo es 3
Para la segunda consulta : 4 pertenece al conjunto {4, 5} y el elemento máximo es 5
Para la tercera consulta: 1 pertenece al conjunto {1, 2, 3} y el elemento máximo es 3
Para la cuarta consulta: 3 pertenece al conjunto {1, 2, 3} y el elemento máximo es 3Entrada: R = 6, arr = {{1, 3}, {2, 4}}, consultas = {2, 5, 6, 1}
Salida: 4 5 6 3
Enfoque: El problema dado se puede resolver utilizando la Unión de conjuntos disjuntos . Inicialmente, todos los elementos están en diferentes conjuntos, procesan el arr[] y realizan la operación de unión en los pares dados y en la actualización de la unión, el valor máximo para cada conjunto en la array, digamos el valor maxValue[] para el elemento principal. Para cada consulta, realice la operación de búsqueda y, para el elemento principal devuelto, busque maxParent[parent] . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector maxValue[] para encontrar el elemento máximo de cada conjunto.
- Inicializa los vectores parent(R+1), rank(R+1, 0), maxValue(R+1) .
- Iterar sobre el rango [1, R+1) usando la variable i y establecer el valor de parent[i] y maxValue[i] como i .
- Iterar sobre el rango [1, N-1] usando la variable i y llamar a la operación de función Union(parent, rank, maxValue, arr[i].first, arr[i].second) .
- Iterar sobre el rango [1, M-1] usando la variable i y realizar los siguientes pasos:
- llamar a la operación de función Find(parent, queries[i]) .
- Imprime el valor de maxValue[i] como el elemento máximo resultante.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3 5 3 3
Complejidad de tiempo: O(N*log M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA