Module: Sistema de conjuntos disjuntos


Problem

1/9

Sistema de conjuntos disjuntos: el comienzo

Theory Click to read/hide

Problem

Escriba un programa que contenga una implementación de una estructura de datos para un conjunto de conjuntos disjuntos (conjuntos disjuntos) de 2 maneras (clasificación heurística y aleatoria)   y procesar solicitudes como esta:
 
RESET n — crear una nueva serie de subconjuntos: un conjunto de solo el elemento 0, solo del elemento 1, y así sucesivamente hasta un conjunto de solo el elemento n–1 inclusive. Si la estructura ya contenía algún otro conjunto de subconjuntos disjuntos, se pierde toda la información relevante. En este caso, se deben mostrar dos palabras en la salida estándar (pantalla) "RESET DONE" separadas por un espacio.
 
ÚNETE jk — combinar los subconjuntos a los que pertenecen el elemento j y el elemento k. Si los elementos ya pertenecían al mismo subconjunto, envíe la palabra "YA" a la salida estándar (pantalla), seguida de los mismos números j y k, separados por espacios, en el mismo orden. Si los elementos hasta ahora pertenecían a diferentes subconjuntos, entonces la acción ocurre solo con los datos en la memoria, no se muestra nada en la pantalla.
 
CHECK jk — verificar si el elemento j y el elemento k pertenecen al mismo subconjunto; enviar la palabra "SÍ" a la salida estándar (pantalla); (si lo hay) o la palabra «NO» (si es diferente).

BREAK: deja de recibir solicitudes.
 
Entrada
La entrada contiene una secuencia de consultas RESET, JOIN y CHECK — cada uno en una línea separada, siguiendo el formato descrito anteriormente. Se garantiza que la primera fila contiene una consulta RESET y que el número total de consultas RESET no supera las 5. El número total de todas las consultas no supera las 200000. El valor de n en cada consulta RESET no supera las 100000. En cada consulta JOIN y en cada consulta CHECK, ambos números estarán en el rango de 0 a n–1, donde n — parámetro de la última solicitud de RESET ejecutada.
 
Salida
Para las consultas RESET, CHECK y JOIN donde los elementos ya pertenecen al mismo subconjunto, muestre el resultado correspondiente (en una línea separada) en la salida estándar (pantalla).
 
Nota
Las respuestas «NO» se dan para solicitudes "CHEQUE 2 11" y "CHEQUE 9 1", la respuesta es "YA 4 1" – a la segunda de las solicitudes "ÚNETE 4 1" (línea 10), "SÍ" – a "COMPROBAR 5 10".
  Entrada Salida
RESTABLECER 15
ÚNETE 14 10
ÚNETE 13 8
ÚNETE 0 9
ÚNETE 8 3
ÚNETE 4 1
ÚNETE 10 5
ÚNETE 8 4
COMPROBAR 2 11
ÚNETE 4 1
ÚNETE 2 6
COMPROBAR 9 1
ÚNETE 6 5
COMPROBAR 10 5
CORTE
RESTABLECER FINALIZADO
NO
YA 4 1
NO
SÍ

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <string>
using namespace std;

long long n, x, y, par[100007], rang[100007];

void make_set(int v) {
	par[v] = v;
	rang[v] = 1;
}

int find_set(int a) {
	if (par[a] == a)
		return a;
	else
		return par[a] = find_set(par[a]);
}

void union_sets(int a, int b) {       
}
int main()
{
	
	string s;
	while (cin >> s) {
		if (s == "BREAK")
			break;
		if (s == "RESET") {
			cin >> n;
			for (int i = 0; i<n; i++) {
				make_set(i);
			}
			cout << "RESET DONE" << endl;
		}
		if (s == "JOIN") {
			cin >> x >> y;
			 if(find_set(x)==find_set(y))
                             cout<<"ALREADY"<<' '<<x<<' '<<y<<endl;
                          else union_sets(x,y);
		}
		if (s == "CHECK") {
			cin >> x >> y;
			if (find_set(x) == find_set(y)) {
				cout << "YES" << endl;
			}
			else {
				cout << "NO" << endl;
			}
		}
	}

}

     

Program check result

To check the solution of the problem, you need to register or log in!