Module: Sistema de conjunto disjunto


Problem

1/9

Sistema de conjuntos disjuntos: o começo

Theory Click to read/hide

Problem

Escreva um programa que contenha uma implementação de uma estrutura de dados para um conjunto de conjuntos disjuntos (conjuntos disjuntos) em 2 maneiras (heurística de classificação e aleatória)   e processar solicitações como esta:
 
RESET n — crie uma nova série de subconjuntos: um conjunto de apenas o elemento 0, de apenas o elemento 1 e assim por diante até um conjunto de apenas o elemento n–1 inclusive. Se a estrutura já contiver algum outro conjunto de subconjuntos disjuntos, toda a informação relevante será perdida. Neste caso, duas palavras devem ser exibidas na saída padrão (tela) "RESET DONE" separadas por um espaço.
 
JUNTAR j k — combine os subconjuntos aos quais o elemento j e o elemento k pertencem. Caso os elementos já pertençam ao mesmo subconjunto, imprima a palavra "JÁ" na saída padrão (tela), seguida dos mesmos números j e k, separados por espaços, na mesma ordem. Se os elementos até então pertenciam a diferentes subconjuntos, então a ação ocorre apenas com os dados na memória, nada é exibido na tela.
 
CHECK j k — verifique se o elemento j e o elemento k pertencem ao mesmo subconjunto; emitir a palavra "SIM" para a saída padrão (tela); (se houver) ou a palavra «NÃO» (se diferente).

BREAK - parar de receber solicitações.
 
Entrada
A entrada contém uma sequência de consultas RESET, JOIN e CHECK — cada um em uma linha separada, seguindo o formato descrito acima. É garantido que a primeira linha contém uma consulta RESET e que o número total de consultas RESET não excede 5. O número total de todas as consultas não excede 200.000. O valor de n em cada consulta RESET não excede 100.000. Em cada JOIN e em cada consulta CHECK, ambos os números estarão no intervalo de 0 a n–1, onde n — parâmetro do último pedido de RESET executado.
 
Saída
Para RESET, CHECK e aquelas consultas JOIN onde os elementos já pertencem ao mesmo subconjunto, exiba o resultado correspondente (em uma linha separada) na saída padrão (tela).
 
Nota
Responda «NÃO» são dadas para pedidos "CHECK 2 11" e "CHECK 9 1", a resposta é "JÁ 4 1" — ao segundo dos pedidos "JOIN 4 1" (10ª linha), "SIM" — para "CHECK 5 10".
 
Entrada Saída
RESET 15
JUNTAR 14 10
JUNTAR 13 8
JUNTAR 0 9
JUNTAR 8 3
JUNTAR 4 1
JUNTAR 10 5
JUNTAR 8 4
VERIFIQUE 2 11
JUNTAR 4 1
JUNTAR 2 6
CHEQUE 9 1
JUNTAR 6 5
CHEQUE 10 5
BREAK
RESET CONCLUÍDO
NÃO
JÁ 4 1
NÃO
SIM

 

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!