Module: Sistema di insiemi disgiunti


Problem

1/9

Sistema di insiemi disgiunti: l'inizio

Theory Click to read/hide

Problem

Scrivi un programma che conterrà un'implementazione di una struttura dati per un insieme di insiemi disgiunti (insiemi disgiunti) in 2 modi (rango euristico e casuale)   ed elaborare richieste come questa:
 
REIMPOSTA n — creare una nuova serie di sottoinsiemi: un insieme di solo elemento 0, di solo elemento 1, e così via fino ad un insieme di solo elemento n-1 compreso. Se la struttura conteneva già qualche altro insieme di sottoinsiemi disgiunti, tutte le informazioni rilevanti vengono perse. In questo caso, sullo standard output (schermata) dovrebbero essere visualizzate due parole "RESET DONE" separate da uno spazio.
 
UNISCITI j k — combinare i sottoinsiemi a cui appartengono l'elemento j e l'elemento k. Se gli elementi appartenevano già allo stesso sottoinsieme, emetti la parola "GIÀ" sullo standard output (schermo), seguita dagli stessi numeri j e k, separati da spazi, nello stesso ordine. Se gli elementi finora appartenevano a diversi sottoinsiemi, allora l'azione si verifica solo con i dati in memoria, sullo schermo non viene visualizzato nulla.
 
CONTROLLA j k — verificare se l'elemento j e l'elemento k appartengono allo stesso sottoinsieme; inviare la parola "SÌ" allo standard output (schermo); (se presente) o la parola «NO» (se diverso).

BREAK - interrompi la ricezione delle richieste.
 
Input
L'input contiene una sequenza di query RESET, JOIN e CHECK — ciascuno su una riga separata, seguendo il formato sopra descritto. È garantito che la prima riga contenga una query RESET e che il numero totale di query RESET non superi 5. Il numero totale di tutte le query non superi 200000. Il valore di n in ogni query RESET non superi 100000. In ogni JOIN query e in ogni query CHECK, entrambi i numeri saranno compresi nell'intervallo da 0 a n–1, dove n — parametro dell'ultima richiesta di RESET eseguita.
 
Uscita
Per RESET, CHECK e quelle query JOIN in cui gli elementi appartengono già allo stesso sottoinsieme, visualizza il risultato corrispondente (in una riga separata) sullo standard output (schermata).
 
Nota
Risponde «NO» sono indicati per le richieste "CHECK 2 11" e "CHECK 9 1", la risposta è "GIÀ 4 1" — alla seconda delle richieste "JOIN 4 1" (10a riga), "SI" — a "CHECK 5 10".
 
Input Uscita
REIMPOSTA 15
ISCRIVITI 14 10
UNISCITI 13 8
UNISCITI 0 9
UNISCITI 8 3
UNISCITI 4 1
UNISCITI 10 5
UNISCITI 8 4
CONTROLLA 2 11
UNISCITI 4 1
UNISCITI 2 6
CONTROLLA 9 1
UNISCITI 6 5
CONTROLLA 10 5
BREAK
RESET FATTO
NO
GIÀ 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!