Dado un entero positivo N que representa el conjunto de enteros [1, N] y una array consultas[] de longitud Q de tipo {L, K} , la tarea es realizar las consultas dadas de acuerdo con las siguientes reglas e imprimir el resultado:
- Si el valor de L es 1 , elimine el entero K dado .
- Si el valor de L es 2 , imprima el primer entero de K a N que no se elimine.
Nota: Cuando se eliminen todos los elementos a la derecha, la respuesta será -1 .
Ejemplos:
Entrada: N = 3, consultas[] = {{2, 1}, {1, 1}, {2, 1}, {2, 3}}
Salida: 1 2 3
Explicación:
Para la primera consulta: el elemento más a la derecha para 1 es 1 solamente.
Después de la segunda consulta: 1 se elimina.
Para la tercera consulta: el elemento más a la derecha para 1 es 2.
Para la cuarta consulta: el elemento más a la derecha para 3 es 3.Entrada: N = 5, consultas = {{2, 1}, {1, 3}, {2, 3}, {1, 2}, {2, 2}, {1, 5}, {2, 5} }
Salida: 1 4 4 -1
Enfoque: el problema dado se puede resolver utilizando la estructura de datos de unión de conjuntos disjuntos . Inicialmente, todos los elementos están en conjuntos diferentes, para el primer tipo de consulta, realice la operación de unión en el entero dado. Para el segundo tipo de consulta, obtenga el padre del vértice dado e imprima el valor almacenado en la array graph[] . Siga los pasos a continuación para resolver el problema:
- Inicialice el gráfico vectorial (N + 2) .
- Iterar sobre el rango [1, N+1] usando la variable i y establecer el valor de graph[i] como i .
- Repita las consultas [] utilizando la consulta variable y realice los siguientes pasos:
- Si query.first es 1 , llame a la operación de función Union(graph, query.second, query.second + 1) .
- De lo contrario, llame a la operación de función Get(graph, query.second) y asígnela a la variable a . Ahora, si el valor de a es (N + 1) , imprima -1 . De lo contrario, imprima el valor de graph[a] como resultado.
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 Get operation
// of disjoint set union
int Get(vector<int>& graph, int a)
{
return graph[a]
= (graph[a] == a ? a
: Get(graph, graph[a]));
}
// Function to perform the union
// operation of disjoint set union
void Union(vector<int>& graph,
int a, int b)
{
a = Get(graph, a);
b = Get(graph, b);
// Update the graph[a] as b
graph[a] = b;
}
// Function to perform given queries on
// set of vertices initially not connected
void Queries(vector<pair<int, int> >& queries,
int N, int M)
{
// Stores the vertices
vector<int> graph(N + 2);
// Mark every vertices rightmost
// vertex as i
for (int i = 1; i <= N + 1; i++) {
graph[i] = i;
}
// Traverse the queries array
for (auto query : queries) {
// Check if it is first type
// of the given query
if (query.first == 1) {
Union(graph, query.second,
query.second + 1);
}
else {
// Get the parent of a
int a = Get(graph, query.second);
// Print the answer for
// the second query
if (a == N + 1)
cout << -1 << " ";
else
cout << graph[a] << " ";
}
}
}
// Driver Code
int main()
{
int N = 5;
vector<pair<int, int> > queries{
{ 2, 1 }, { 1, 1 }, { 2, 1 }, { 2, 3 }
};
int Q = queries.size();
Queries(queries, N, Q);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to perform the Get operation
// of disjoint set union
public static int Get(int[] graph, int a)
{
return graph[a]
= (graph[a] == a ? a
: Get(graph, graph[a]));
}
// Function to perform the union
// operation of disjoint set union
public static void Union(int[] graph,
int a, int b)
{
a = Get(graph, a);
b = Get(graph, b);
// Update the graph[a] as b
graph[a] = b;
}
// Function to perform given queries on
// set of vertices initially not connected
public static void Queries(int[][] queries,
int N, int M)
{
// Stores the vertices
int[] graph = new int[N + 2];
// Mark every vertices rightmost
// vertex as i
for (int i = 1; i <= N + 1; i++) {
graph[i] = i;
}
// Traverse the queries array
for (int[] query : queries) {
// Check if it is first type
// of the given query
if (query[0] == 1) {
Union(graph, query[1],
query[1] + 1);
}
else {
// Get the parent of a
int a = Get(graph, query[1]);
// Print the answer for
// the second query
if (a == N + 1)
System.out.print(-1);
else
System.out.print(graph[a] + " ");
}
}
}
// Driver Code
public static void main(String args[])
{
int N = 5;
int[][] queries = { { 2, 1 }, { 1, 1 }, { 2, 1 }, { 2, 3 }};
int Q = queries.length;
Queries(queries, N, Q);
}
}
// This code is contributed by gfgking.
Python3
# Python 3 program for the above approach # Function to perform the Get operation # of disjoint set union def Get(graph, a): if graph[graph[a]]!= graph[a]: graph[a] = Get(graph, graph[a]) else: return graph[a] # Function to perform the union # operation of disjoint set union def Union(graph, a, b): a = Get(graph, a) b = Get(graph, b) # Update the graph[a] as b graph[a] = b # Function to perform given queries on # set of vertices initially not connected def Queries(queries, N, M): # Stores the vertices graph = [0 for i in range(N + 2)] # Mark every vertices rightmost # vertex as i for i in range(1,N + 2,1): graph[i] = i # Traverse the queries array for query in queries: # Check if it is first type # of the given query if (query[0] == 1): Union(graph, query[1], query[1] + 1) else: # Get the parent of a a = Get(graph, query[1]) # Print the answer for # the second query if (a == N + 1): print(-1) else: print(graph[a],end = " ") # Driver Code if __name__ == '__main__': N = 5 queries = [[2, 1],[1, 1],[2, 1],[2, 3]] Q = len(queries) Queries(queries, N, Q) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to perform the Get operation
// of disjoint set union
function Get(graph, a) {
return (graph[a] = graph[a] == a ? a : Get(graph, graph[a]));
}
// Function to perform the union
// operation of disjoint set union
function Union(graph, a, b) {
a = Get(graph, a);
b = Get(graph, b);
// Update the graph[a] as b
graph[a] = b;
}
// Function to perform given queries on
// set of vertices initially not connected
function Queries(queries, N, M) {
// Stores the vertices
let graph = new Array(N).fill(2);
// Mark every vertices rightmost
// vertex as i
for (let i = 1; i <= N + 1; i++) {
graph[i] = i;
}
// Traverse the queries array
for (let query of queries) {
// Check if it is first type
// of the given query
if (query[0] == 1) {
Union(graph, query[1], query[1] + 1);
} else {
// Get the parent of a
let a = Get(graph, query[1]);
// Print the answer for
// the second query
if (a == N + 1) document.write(-1 + " ");
else document.write(graph[a] + " ");
}
}
}
// Driver Code
let N = 5;
let queries = [
[2, 1],
[1, 1],
[2, 1],
[2, 3],
];
let Q = queries.length;
Queries(queries, N, Q);
// This code is contributed by gfgking.
</script>
1 2 3
Complejidad de tiempo: O(M*log N)
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