Module: Système d'ensemble disjoint


Problem

1/9

Système d'ensembles disjoints : le début

Theory Click to read/hide

Problem

Écrire un programme qui contiendra une implémentation d'une structure de données pour un ensemble d'ensembles disjoints (ensembles disjoints) de 2 manières (heuristique de rang et aléatoire)  ;  et traiter les demandes comme ceci :
 
RESET n — créer une nouvelle série de sous-ensembles : un ensemble de l'élément 0 uniquement, de l'élément 1 uniquement, et ainsi de suite jusqu'à un ensemble de l'élément n-1 inclus. Si la structure contenait déjà un autre ensemble de sous-ensembles disjoints, toutes les informations pertinentes sont perdues. Dans ce cas, deux mots doivent être affichés sur la sortie standard (écran) "RESET DONE" séparés par un espace.
 
JOIN j k — combiner les sous-ensembles auxquels appartiennent l'élément j et l'élément k. Si les éléments appartenaient déjà au même sous-ensemble, sortir le mot "DEJA" sur la sortie standard (écran), suivi des mêmes nombres j et k, séparés par des espaces, dans le même ordre. Si les éléments appartenaient jusqu'à présent à des sous-ensembles différents, alors l'action ne se produit qu'avec les données en mémoire, rien ne s'affiche à l'écran.
 
VÉRIFIER j k — vérifier si l'élément j et l'élément k appartiennent au même sous-ensemble ; émettre le mot "OUI" sur la sortie standard (écran) ; (le cas échéant) ou le mot «NON» (si différent).

BREAK – Ne plus recevoir de demandes.
 
Entrée
L'entrée contient une séquence de requêtes RESET, JOIN et CHECK — chacun sur une ligne distincte, en suivant le format décrit ci-dessus. Il est garanti que la première ligne contient une requête RESET et que le nombre total de requêtes RESET ne dépasse pas 5. Le nombre total de toutes les requêtes ne dépasse pas 200 000. La valeur de n dans chaque requête RESET ne dépasse pas 100 000. Dans chaque Requête JOIN et dans chaque requête CHECK, les deux nombres seront compris entre 0 et n–1, où n — paramètre de la dernière requête RESET exécutée.
 
Sortie
Pour les requêtes RESET, CHECK et JOIN où les éléments appartiennent déjà au même sous-ensemble, affichez le résultat correspondant (dans une ligne séparée) sur la sortie standard (écran).
 
Remarque
Répondez «NON» sont donnés pour les requêtes "CHECK 2 11" et "CHECK 9 1", la réponse est "DÉJÀ 4 1" — à la seconde des requêtes "JOIN 4 1" (10ème ligne), "OUI" — à "CHECK 5 10".
 
RÉINITIALISER 15
JOIGNEZ-VOUS 14 10
REJOINDRE 13 8
REJOINDRE 0 9
REJOINDRE 8 3
JOIGNEZ-VOUS 4 1
JOIGNEZ-VOUS 10 5
JOIGNEZ-VOUS 8 4
VÉRIFICATION 2 11
JOIGNEZ-VOUS 4 1
JOIGNEZ-VOUS 2 6
VÉRIFICATION 9 1
JOIGNEZ-VOUS 6 5
VÉRIFICATION 10 5
PAUSE
RÉINITIALISATION EFFECTUÉE
NON
DÉJÀ 4 1
NON
OUI
Entrée Sortie

 

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!