Problem

1/9

डिसजॉइंट सेट सिस्टम: शुरुआत

Theory Click to read/hide

Problem

एक ऐसा प्रोग्राम लिखें जिसमें दो तरीकों (अनुमानित और यादृच्छिक रैंक)   और अनुरोधों को इस प्रकार संसाधित करें:
 
रीसेट एन — उपसमुच्चय की एक नई श्रृंखला बनाएं: केवल तत्व 0 का एक सेट, केवल तत्व 1 का, और इसी तरह केवल तत्व n–1 सहित के सेट तक। यदि संरचना में पहले से ही असंयुक्त उपसमुच्चय का कुछ अन्य सेट शामिल है, तो सभी प्रासंगिक जानकारी खो जाती है। इस मामले में, दो शब्दों को मानक आउटपुट (स्क्रीन) "रीसेट हो गया" पर एक स्थान से अलग करके प्रदर्शित किया जाना चाहिए।
 
जॉइन जे के — तत्व j और तत्व k से संबंधित सबसेट को संयोजित करें। यदि तत्व पहले से ही एक ही सबसेट से संबंधित हैं, तो मानक आउटपुट (स्क्रीन) पर "ALREADY" शब्द को आउटपुट करें, उसके बाद समान संख्या j और k, रिक्त स्थान द्वारा अलग किए गए, उसी क्रम में। यदि तत्व अब तक अलग-अलग उपसमुच्चयों से संबंधित थे, तो क्रिया केवल स्मृति में डेटा के साथ होती है, स्क्रीन पर कुछ भी प्रदर्शित नहीं होता है।
 
जे के चेक करें — जाँच करें कि क्या तत्व j और तत्व k एक ही उपसमुच्चय से संबंधित हैं; मानक आउटपुट (स्क्रीन) पर "YES" शब्द आउटपुट करें; (यदि कोई हो) या शब्द «नहीं» (यदि भिन्न हो).

BREAK - अनुरोध प्राप्त करना बंद करें।
 
इनपुट
इनपुट में RESET, JOIN, और CHECK प्रश्नों का क्रम होता है — ऊपर वर्णित प्रारूप के बाद प्रत्येक एक अलग लाइन पर। यह गारंटी है कि पहली पंक्ति में एक RESET क्वेरी है और RESET प्रश्नों की कुल संख्या 5 से अधिक नहीं है। सभी प्रश्नों की कुल संख्या 200000 से अधिक नहीं है। प्रत्येक RESET क्वेरी में n का मान 100000 से अधिक नहीं है। प्रत्येक में JOIN क्वेरी और प्रत्येक चेक क्वेरी में, दोनों संख्याएँ 0 से n–1 की सीमा में होंगी, जहाँ n — अंतिम निष्पादित RESET अनुरोध का पैरामीटर।
 
आउटपुट
रीसेट, चेक और उन जॉइन प्रश्नों के लिए जहां तत्व पहले से ही एक ही सबसेट से संबंधित हैं, मानक आउटपुट (स्क्रीन) पर संबंधित परिणाम (एक अलग लाइन में) प्रदर्शित करें।
 
ध्यान दें
जवाब «नहीं» अनुरोधों के लिए दिए गए हैं "चेक 2 11" और "9 1 की जाँच करें", उत्तर "पहले से ही 4 1" है — अनुरोध के दूसरे अनुरोध के लिए "4 1 में शामिल हों" (10वीं पंक्ति), "हाँ" — "5 10 चेक करें" के लिए।
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स"> <शरीर> इनपुट आउटपुट <टीडी>
रीसेट 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
ब्रेक
<टीडी>
रीसेट हो गया
नहीं
पहले से ही 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!