Module: System nicht überlappender Mengen


Problem

1/9

Das System der sich nicht überlappenden Mengen: Der Anfang

Theory Click to read/hide

Problem

Schreiben Sie ein Programm, das eine Datenstruktur-Implementierung für eine Reihe von nicht überlappenden Teilmengen (disjoint sets) enthält auf zwei Arten (Rang-Heuristik und zufällig)   und verarbeiten Sie Abfragen solcher Arten:
 
RESET n — erstelle eine neue Reihe von Teilmengen: eine Menge von nur einem Element 0, von nur einem Element 1 und so bis zu einer Menge von nur einem Element n–1 inklusive. Wenn die Struktur bereits eine andere Sammlung nicht überlappender Teilmengen enthielt, gehen alle relevanten Informationen verloren. Zum Standardausgang (Bildschirm) müssen Sie dabei zwei Wörter durch ein Leerzeichen «RESET DONE» ausgeben.
 
JOIN j k — Kombinieren Sie die Teilmengen, zu denen das Element j und das Element k gehören. Wenn die Elemente bereits zu derselben Teilmenge gehören, geben Sie das Wort «ALREADY» an die Standardausgabe (Bildschirm) aus, gefolgt von Leerzeichen durch die gleichen Zahlen j und k in der gleichen Reihenfolge aus. Wenn die Elemente bisher zu verschiedenen Teilmengen gehörten, erfolgt die Aktion nur mit den Daten im Speicher, es wird nichts auf dem Bildschirm angezeigt.
 
CHECK j k — prüfen, ob Element j und Element k zu einer Teilmenge gehören; Geben Sie das Wort «YES» (wenn es eins ist) oder das Wort «NO» (wenn es anders ist) an die Standardausgabe (Bildschirm) aus.

BREAK - Beenden Sie den Empfang von Anfragen.
 
Eingabe
Die Eingabe enthält eine Abfolge von RESET-, JOIN- und CHECK-Abfragen, die jeweils in einer separaten Zeile gemäß dem oben beschriebenen Format angezeigt werden. Es ist garantiert, dass die erste Zeile eine RESET-Anforderung enthält und die Gesamtzahl der RESET-Anforderungen nicht mehr als 5 beträgt. Die Gesamtzahl aller Anfragen überschreitet 200.000 nicht. Der Wert von n in jeder RESET-Anforderung überschreitet nicht 100000. In jeder JOIN-Abfrage und in jeder CHECK-Abfrage liegen beide Zahlen zwischen 0 und n–1, wobei n — der Parameter der zuletzt ausgeführten RESET-Anforderung ist.
 
Ausgabe
Für RESET-, CHECK- und JOIN-Abfragen, bei denen Elemente bereits zu einer Teilmenge gehören, wird das entsprechende Ergebnis (in einer separaten Zeile) an die Standardausgabe (Bildschirm) ausgegeben.
 
Hinweis
Die Antworten «NO» werden auf Anfragen von «CHECK 2 11» und «CHECK 9 1» gegeben, die Antwort «ALREADY 4 1» — auf die zweite der Anfragen von «JOIN 4 1» (10. Zeile), «YES» — auf «CHECK 5 10».
 
Eingabe Ausgabe
RESET 15
JOIN 14 10
JOIN 13 8
JOIN 0 9
JOIN 8 3
JOIN 4 1
JOIN 10 5
JOIN 8 4
CHECK 2 11
JOIN 4 1
JOIN 2 6
CHECK 9 1
JOIN 6 5
CHECK 10 5
BREAK
RESET DONE
NO
ALREADY 4 1
NO
YES

 

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!