Module: 素集合系


Problem

1/9

ばらばらな集合システム: はじまり

Theory Click to read/hide

Problem

2 つの方法 (ランク ヒューリスティックおよびランダム) で素集合 (素集合) のデータ構造の実装を含むプログラムを作成します。  次のようなリクエストを処理します:
 
RESET n —新しい一連のサブセットを作成します。要素 0 のみのセット、要素 1 のみのセットなど、要素 n–1 のみのセットまで続きます。構造体に他のばらばらのサブセットのセットが既に含まれている場合、関連するすべての情報が失われます。この場合、標準出力 (画面) に「RESET DONE」という 2 つの単語がスペースで区切られて表示されます。
 
JOIN j k —要素 j と要素 k が属するサブセットを結合します。要素がすでに同じサブセットに属している場合は、単語 "ALREADY" を標準出力 (画面) に出力し、その後に同じ番号 j と k をスペースで区切って同じ順序で出力します。これまでの要素が異なるサブセットに属していた場合、アクションはメモリ内のデータでのみ発生し、画面には何も表示されません。
 
チェック j k —要素 j と要素 k が同じサブセットに属しているかどうかを確認します。 "YES" という単語を標準出力 (画面) に出力します。 (ある場合) または単語 «NO» (異なる場合)

BREAK - リクエストの受信を停止します。
 
入力
入力には、一連の RESET、JOIN、および CHECK クエリが含まれています —上記の形式に従って、それぞれを別の行に入力します。最初の行に RESET クエリが含まれ、RESET クエリの総数が 5 を超えないことが保証されています。すべてのクエリの総数が 200000 を超えていません。各 RESET クエリの n の値は 100000 を超えていません。 JOIN クエリと各 CHECK クエリでは、両方の数値が 0 から n–1 の範囲になります。ここで n —最後に実行された RESET リクエストのパラメータ。
 
出力
要素がすでに同じサブセットに属している RESET、CHECK、およびそれらの JOIN クエリの場合、対応する結果を (別の行に) 標準出力 (画面) に表示します。
 
注意
「いいえ」と答えるリクエスト「CHECK 2 11」に対して与えられますと「CHECK 9 1」、答えは「ALREADY 4 1」 — 2番目のリクエスト「JOIN 4 1」に(10行目)、「はい」 — 「CHECK 5 10」へ
  <本体>
 

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++
入力 出力
リセット 15
14 10 に参加
13 8 に参加
0 9 に参加
8 3 に参加
4 1 に参加
10 5に参加
8 4 に参加
チェック 2 11
4 1 に参加
JOIN 2 6
チェック 9 1
6 5 に参加
チェック 10 5
ブレイク
リセット完了
いいえ
すでに 4 1
いいえ
はい
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!