Module: Hệ thống tập hợp rời rạc


Problem

1/9

Hệ thống tập hợp rời rạc: Sự khởi đầu

Theory Click to read/hide

Problem

Viết một chương trình sẽ bao gồm việc triển khai cấu trúc dữ liệu cho một tập hợp các tập hợp rời rạc (các tập hợp rời rạc) theo 2 cách (xếp hạng heuristic và ngẫu nhiên)   và xử lý các yêu cầu như sau:
 
ĐẶT LẠI n — tạo một chuỗi tập hợp con mới: tập hợp chỉ gồm phần tử 0, chỉ phần tử 1, v.v. cho đến tập hợp chỉ bao gồm n–1 phần tử. Nếu cấu trúc đã chứa một số tập hợp con rời rạc khác, thì tất cả thông tin liên quan sẽ bị mất. Trong trường hợp này, hai từ sẽ được hiển thị trên đầu ra tiêu chuẩn (màn hình) "RESET DONE" được phân tách bằng dấu cách.
 
THAM GIA j k — kết hợp các tập con mà phần tử j và phần tử k thuộc về. Nếu các phần tử đã thuộc về cùng một tập hợp con, hãy xuất từ ​​"ALREADY" sang đầu ra tiêu chuẩn (màn hình), theo sau là các số j và k giống nhau, được phân tách bằng dấu cách, theo cùng một thứ tự. Nếu các phần tử cho đến nay thuộc về các tập hợp con khác nhau, thì hành động chỉ xảy ra với dữ liệu trong bộ nhớ, không có gì hiển thị trên màn hình.
 
KIỂM TRA j k — kiểm tra xem phần tử j và phần tử k có thuộc cùng một tập con hay không; xuất từ ​​"YES" ra đầu ra tiêu chuẩn (màn hình); (nếu có) hoặc từ «KHÔNG» (nếu khác).

BREAK - ngừng nhận yêu cầu.
 
Đầu vào
Đầu vào chứa một chuỗi các truy vấn ĐẶT LẠI, THAM GIA và KIỂM TRA — mỗi dòng trên một dòng riêng biệt, theo định dạng được mô tả ở trên. Đảm bảo rằng hàng đầu tiên chứa truy vấn CÀI ĐẶT LẠI và tổng số truy vấn CÀI ĐẶT LẠI không vượt quá 5. Tổng số của tất cả các truy vấn không vượt quá 200000. Giá trị của n trong mỗi truy vấn CÀI ĐẶT LẠI không vượt quá 100000. Trong mỗi truy vấn THAM GIA truy vấn và trong mỗi truy vấn KIỂM TRA, cả hai số sẽ nằm trong phạm vi từ 0 đến n–1, trong đó n — tham số của yêu cầu CÀI ĐẶT LẠI được thực hiện lần cuối.
 
Đầu ra
Đối với các truy vấn ĐẶT LẠI, KIỂM TRA và các truy vấn THAM GIA trong đó các phần tử đã thuộc về cùng một tập hợp con, hãy hiển thị kết quả tương ứng (trong một dòng riêng biệt) trên đầu ra (màn hình) tiêu chuẩn.
 
Lưu ý
Câu trả lời "KHÔNG" được đưa ra cho các yêu cầu "KIỂM TRA 2 11" và "KIỂM TRA 9 1", đáp án là "ALREADY 4 1" — đến lần thứ hai trong số các yêu cầu "THAM GIA 4 1" (dòng thứ 10), "CÓ" — đến "KIỂM TRA 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++
Đầu vào Đầu ra
ĐẶT LẠI 15
THAM GIA 14 10
THAM GIA 13 8
THAM GIA 0 9
THAM GIA 8 3
THAM GIA 4 1
THAM GIA 10 5
THAM GIA 8 4
KIỂM TRA 2 11
THAM GIA 4 1
THAM GIA 2 6
KIỂM TRA 9 1
THAM GIA 6 5
KIỂM TRA 10 5
BREAK
XONG THIẾT LẬP LẠI
KHÔNG
ĐÃ ĐÃ 4 1
KHÔNG
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!