Module: سیستم مجموعه ای از هم گسسته


Problem

1/9

Disjoint Set System: The Beginning

Theory Click to read/hide

Problem

برنامه ای بنویسید که شامل اجرای یک ساختار داده برای مجموعه ای از مجموعه های غیرمتناسب (مجموعه های ناهمگون) به 2 روش (رتبه اکتشافی و تصادفی) باشد   و درخواست ها را مانند این پردازش کنید:
 
تنظیم مجدد n — یک سری جدید از زیر مجموعه ها ایجاد کنید: مجموعه ای از فقط عنصر 0، تنها عنصر 1، و به همین ترتیب تا مجموعه ای از تنها عنصر n–1 شامل. اگر ساختار قبلاً شامل مجموعه دیگری از زیرمجموعه های مجزا باشد، تمام اطلاعات مربوطه از بین می رود. در این مورد، دو کلمه باید روی خروجی استاندارد (صفحه نمایش) "RESET DONE" که با فاصله از هم جدا شده اند، نمایش داده شود.
 
JoIN j k — زیر مجموعه هایی را که عنصر j و عنصر k به آنها تعلق دارند را با هم ترکیب کنید. اگر عناصر قبلاً به یک زیرمجموعه تعلق داشتند، کلمه "ALREADY" را به خروجی استاندارد (صفحه نمایش) و به دنبال آن همان اعداد j و k را که با فاصله از هم جدا شده اند، به همان ترتیب خارج کنید. اگر عناصر تا کنون متعلق به زیرمجموعه‌های مختلف بوده‌اند، این عمل فقط با داده‌های موجود در حافظه انجام می‌شود، چیزی روی صفحه نمایش داده نمی‌شود.
 
j k — بررسی کنید که آیا عنصر j و عنصر k به یک زیر مجموعه تعلق دارند یا خیر. خروجی کلمه "YES" به خروجی استاندارد (صفحه نمایش)؛ (اگر یکی) یا کلمه «نه» (اگر متفاوت باشد).

BREAK - دریافت درخواست‌ها را متوقف کنید.
 
ورودی
ورودی شامل دنباله ای از پرس و جوهای RESET، JOIN و CHECK — هر کدام در یک خط جداگانه، به دنبال قالب توضیح داده شده در بالا. تضمین می شود که سطر اول شامل یک عبارت RESET باشد و تعداد کل پرس و جوهای RESET از 5 تجاوز نکند. تعداد کل همه پرس و جوها از 200000 تجاوز نمی کند. JOIN query و در هر جستار CHECK، هر دو اعداد در محدوده 0 تا n–1 خواهند بود، جایی که n — پارامتر آخرین درخواست RESET اجرا شده.
 
خروجی
برای RESET، CHECK و آن دسته از جستارهای JOIN که عناصر از قبل به یک زیر مجموعه تعلق دارند، نتیجه مربوطه را (در یک خط جداگانه) در خروجی استاندارد (صفحه) نمایش دهید.
 
یادداشت
پاسخ ها «نه» برای درخواست ها داده می شود "بررسی 2 11" و "بررسی 9 1"، پاسخ "در حال حاضر 4 1" است — به دومین درخواست "JOIN 4 1" (خط دهم)، "بله" — به "بررسی 5 10".
  <بدن>
ورودی خروجی
تنظیم مجدد 15
به 14 10 بپیوندید
به 13 8 بپیوندید
به 0 9 بپیوندید
به 8 3 بپیوندید
به 4 1 بپیوندید
به 10 5 بپیوندید
به 8 4 بپیوندید
2 11 را بررسی کنید
به 4 1 بپیوندید
به 2 6 بپیوندید
9 1
را بررسی کنید
به 6 5 بپیوندید
بررسی 10 5
BREAK
بازنشانی انجام شد
نه
قبلاً 4 1
نه
بله

 

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!