Module: Disjoint set system


Problem

1/9

Disjoint Set System: The Beginning

Theory Click to read/hide

Problem

Write a program that will contain an implementation of a data structure for a set of disjoint sets (disjoint sets) in 2 ways (rank heuristic and random)   and process requests like this:
 
RESET n — create a new series of subsets: a set of only element 0, of only element 1, and so on up to a set of only element n–1 inclusive. If the structure already contained some other set of disjoint subsets, all relevant information is lost. In this case, two words should be displayed on the standard output (screen) "RESET DONE" separated by a space.
 
JOIN j k — combine the subsets that the element j and the element k belong to. If the elements already belonged to the same subset, output the word "ALREADY" to the standard output (screen), followed by the same numbers j and k, separated by spaces, in the same order. If the elements so far belonged to different subsets, then the action occurs only with the data in memory, nothing is displayed on the screen.
 
CHECK j k — check whether element j and element k belong to the same subset; output the word "YES" to the standard output (screen); (if one) or the word «NO» (if different).

BREAK - stop receiving requests.
 
Input
The input contains a sequence of RESET, JOIN, and CHECK queries — each on a separate line, following the format described above. It is guaranteed that the first row contains a RESET query and that the total number of RESET queries does not exceed 5. The total number of all queries does not exceed 200000. The value of n in each RESET query does not exceed 100000. In each JOIN query and in each CHECK query, both numbers will be in the range from 0 to n–1, where n — parameter of the last executed RESET request.
 
Output
For RESET, CHECK and those JOIN queries where the elements already belong to the same subset, display the corresponding result (in a separate line) on the standard output (screen).
 
Note
Answers «NO» are given for requests "CHECK 2 11" and "CHECK 9 1", the answer is "ALREADY 4 1" — to the second of the requests "JOIN 4 1" (10th line), "YES" — to "CHECK 5 10".
 
Input Output
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!