Dada una array de pares arr[][] de longitud N , y una array queries[] de longitud M , y un entero R , donde cada consulta contiene un entero de 1 a R , la tarea para cada consulta[i] es encontrar el conjunto al que pertenece y encontrar el número total de elementos del conjunto.
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 2 3 3
Explicación :
Después de hacer los conjuntos de los pares arr[], {1, 2, 3}, {4, 5}
Para la primera consulta: 2 pertenece al conjunto {1, 2, 3} y el número total de elementos es 3 Para la segunda consulta :
4 pertenece al conjunto {4, 5} y el número total de elementos es 2.
Para la tercera consulta: 1 pertenece al conjunto {1, 2, 3} y el número total de elementos es 3 Para la cuarta consulta :
3 pertenece al conjunto {1, 2, 3} y el número total de elementos es 3.Entrada: R = 6, arr[] = {{1, 3}, {2, 4}}, consultas[] = {2, 5, 6, 1}
Salida: 2 1 1 2
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 total[] para el elemento principal. Para cada consulta, encuentre la operación y para el elemento principal devuelto, encuentre el tamaño del conjunto actual como el valor de total[parent] . Siga los pasos a continuación para resolver el problema:
- Inicializa los vectores parent(R + 1) , rank(R + 1, 0) , total(R + 1, 1) .
- Iterar sobre el rango [1, R+1) usando la variable i y establecer el valor de parent[I] como I .
- Iterar sobre el rango [1, N-1] usando la variable i y realizar la operación de unión como Union(parent, rank, total, arr[I].first, arr[I].second) .
- Iterar sobre el rango [1, M – 1] usando la variable i y realizar los siguientes pasos:
- Llame a la función para encontrar el padre del elemento actual consultas[i] como Find(parent, queries[I]) .
- Imprime el valor de total[i] como el tamaño del conjunto actual.
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
// of disjoint set union
int Find(vector<int>& parent, int a)
{
return parent[a]
= (parent[a] == a)
? a
: (Find(parent, parent[a]));
}
// Function to find the Union operation
// of disjoint set union
void Union(vector<int>& parent,
vector<int>& rank,
vector<int>& total,
int a, int b)
{
// Find the parent of a and 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;
}
// Update the parent for node b
parent[b] = a;
// Update the total number of
// elements of a
total[a] += total[b];
}
// Function to find the total element
// of the set which belongs to the
// element queries[i]
void findTotNumOfSet(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 total number of
// elements of the sets
vector<int> total(R + 1, 1);
for (int i = 1; i < R + 1; i++) {
// Update parent[i] to i
parent[i] = i;
}
for (int i = 0; i < N; i++) {
// Add the arr[i].first and
// arr[i].second elements to
// the same set
Union(parent, rank, total,
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 total elements of
// the set which belongs to P
cout << total[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();
findTotNumOfSet(arr, queries, R, N, M);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to perform the find operation
// of disjoint set union
static int Find(int [] parent, int a)
{
return parent[a]
= (parent[a] == a)
? a
: (Find(parent, parent[a]));
}
// Function to find the Union operation
// of disjoint set union
static void Union(int [] parent,
int [] rank,
int [] total,
int a, int b)
{
// Find the parent of a and 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;
}
// Update the parent for node b
parent[b] = a;
// Update the total number of
// elements of a
total[a] += total[b];
}
// Function to find the total element
// of the set which belongs to the
// element queries[i]
static void findTotNumOfSet(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 total number of
// elements of the sets
int [] total = new int[R + 1];
for (int i = 0; i < total.length; i++) {
total[i] = 1;
}
for (int i = 1; i < R + 1; i++) {
// Update parent[i] to i
parent[i] = i;
}
for (int i = 0; i < N; i++) {
// Add the arr[i][0] and
// arr[i][1] elements to
// the same set
Union(parent, rank, total,
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 total elements of
// the set which belongs to P
System.out.print(total[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;
findTotNumOfSet(arr, queries, R, N, M);
}
}
// This code is contributed by 29AjayKumar.
Python3
# Python3 program for the above approach # Function to perform the find operation # of disjoint set union def Find(parent, a): if (parent[a] == a): return a else: return Find(parent, parent[a]) # Function to find the Union operation # of disjoint set union def Union(parent, rank, total, a, b): # Find the parent of a and 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 # Update the parent for node b parent[b] = a # Update the total number of # elements of a total[a] += total[b] # Function to find the total element # of the set which belongs to the # element queries[i] def findTotNumOfSet(arr, queries, R, N, M): # Stores the parent elements # of the sets parent = [None]*(R+1) # Stores the rank of the sets rank = [0]*(R+1) # Stores the total number of # elements of the sets total = [1]*(R + 1) for i in range(1, R + 1): # Add the arr[i].first and # arr[i].second elements to # the same set parent[i] = i for i in range(N): Union(parent, rank, total, 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 total elements of # the set which belongs to P print(total[P], end=" ") # Driver code R = 5 arr = [[1, 2], [2, 3], [4, 5]] queries = [2, 4, 1, 3] N = len(arr) M = len(queries) findTotNumOfSet(arr, queries, R, N, M) # This code is contributed by parthmanchanda81
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to perform the find operation
// of disjoint set union
static int Find(int [] parent, int a)
{
return parent[a]
= (parent[a] == a)
? a
: (Find(parent, parent[a]));
}
// Function to find the Union operation
// of disjoint set union
static void Union(int [] parent,
int [] rank,
int [] total,
int a, int b)
{
// Find the parent of a and 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;
}
// Update the parent for node b
parent[b] = a;
// Update the total number of
// elements of a
total[a] += total[b];
}
// Function to find the total element
// of the set which belongs to the
// element queries[i]
static void findTotNumOfSet(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 total number of
// elements of the sets
int [] total = new int[R + 1];
for (int i = 0; i < total.Length; i++) {
total[i] = 1;
}
for (int i = 1; i < R + 1; i++) {
// Update parent[i] to i
parent[i] = i;
}
for (int i = 0; i < N; i++) {
// Add the arr[i,0] and
// arr[i,1] elements to
// the same set
Union(parent, rank, total,
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 total elements of
// the set which belongs to P
Console.Write(total[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.GetLength(0);
findTotNumOfSet(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
// of disjoint set union
function Find(parent, a)
{
return (parent[a] = parent[a] == a ? a : Find(parent, parent[a]));
}
// Function to find the Union operation
// of disjoint set union
function Union(parent, rank, total, a, b)
{
// Find the parent of a and 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;
}
// Update the parent for node b
parent[b] = a;
// Update the total number of
// elements of a
total[a] += total[b];
}
// Function to find the total element
// of the set which belongs to the
// element queries[i]
function findTotNumOfSet(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 total number of
// elements of the sets
let total = new Array(R + 1).fill(1);
for (let i = 1; i < R + 1; i++)
{
// Update parent[i] to i
parent[i] = i;
}
for (let i = 0; i < N; i++)
{
// Add the arr[i].first and
// arr[i].second elements to
// the same set
Union(parent, rank, total, 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 total elements of
// the set which belongs to P
document.write(total[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;
findTotNumOfSet(arr, queries, R, N, M);
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
3 2 3 3
Complejidad temporal: O(M*log R)
Espacio auxiliar: O(R)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA