Module: نظام مجموعة منفصلة


Problem

1/9

نظام المجموعة المنفصلة: البداية

Theory Click to read/hide

Problem

اكتب برنامجًا يحتوي على تنفيذ بنية بيانات لمجموعة من المجموعات المنفصلة (مجموعات منفصلة) بطريقتين (ترتيب إرشادي وعشوائي) & nbsp؛ & nbsp؛ ومعالجة الطلبات مثل هذا:
& nbsp؛
إعادة تعيين n & [مدش] ؛ قم بإنشاء سلسلة جديدة من المجموعات الفرعية: مجموعة من العنصر 0 فقط ، من العنصر 1 فقط ، وهكذا حتى مجموعة من العناصر فقط n & ndash؛ 1 شاملة. إذا احتوى الهيكل بالفعل على مجموعة أخرى من المجموعات الفرعية المنفصلة ، يتم فقد جميع المعلومات ذات الصلة. في هذه الحالة ، يجب عرض كلمتين على الإخراج القياسي (الشاشة) "RESET DONE" مفصولة بمسافة.
& nbsp؛
JOIN j k & mdash؛ اجمع بين المجموعات الفرعية التي ينتمي إليها العنصر j والعنصر k. إذا كانت العناصر تنتمي بالفعل إلى نفس المجموعة الفرعية ، فقم بإخراج كلمة "ALREADY" إلى الإخراج القياسي (الشاشة) ، متبوعًا بنفس الأرقام j و k ، مفصولة بمسافات ، بنفس الترتيب. إذا كانت العناصر حتى الآن تنتمي إلى مجموعات فرعية مختلفة ، فسيحدث الإجراء فقط مع البيانات الموجودة في الذاكرة ، ولن يتم عرض أي شيء على الشاشة.
& nbsp؛
تحقق j k & [مدش]؛ تحقق مما إذا كان العنصر j والعنصر k ينتميان إلى نفس المجموعة الفرعية ؛ إخراج كلمة "نعم" إلى الإخراج القياسي (الشاشة) ؛ (إن وجد) أو كلمة "لا". (إذا كان مختلفًا).

BREAK - إيقاف استقبال الطلبات.
نبسب ؛
إدخال
يحتوي الإدخال على سلسلة من استعلامات RESET و JOIN و CHECK & [مدش]؛ كل على سطر منفصل ، باتباع التنسيق الموضح أعلاه. من المضمون أن يحتوي الصف الأول على استعلام RESET وأن العدد الإجمالي لاستعلامات RESET لا يتجاوز 5. العدد الإجمالي لجميع الاستعلامات لا يتجاوز 200000. لا تتجاوز قيمة n في كل استعلام RESET 100000. في كل منها استعلام JOIN وفي كل استعلام CHECK ، سيكون كلا الرقمين في النطاق من 0 إلى n & ndash؛ 1 ، حيث n & mdash؛ معلمة آخر طلب RESET تم تنفيذه.
& nbsp؛
الإخراج
بالنسبة إلى استعلامات RESET و CHECK واستعلامات JOIN حيث تنتمي العناصر بالفعل إلى نفس المجموعة الفرعية ، اعرض النتيجة المقابلة (في سطر منفصل) على الإخراج القياسي (الشاشة).
& nbsp؛
ملاحظة
الإجابات & laquo؛ NO & raquo؛ يتم تقديمها للطلبات "CHECK 2 11" و "CHECK 9 1" ، الإجابة هي "بالفعل 4 1" و [مدش]. إلى ثاني الطلبات "JOIN 4 1" (السطر العاشر) ، "نعم" و [مدش]. إلى "CHECK 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!