Module: ayrık küme sistemi


Problem

1/9

Ayrık Küme Sistemi: Başlangıç

Theory Click to read/hide

Problem

Bir ayrık kümeler kümesi (ayrık kümeler) için bir veri yapısının uygulanmasını 2 şekilde (sıralama buluşsal ve rastgele) içerecek bir program yazın   ve istekleri şu şekilde işleyin:
 
RESET n — yeni bir alt küme dizisi oluşturun: yalnızca 0 öğesinden, yalnızca 1 öğesinden oluşan bir küme ve yalnızca n–1 öğesi dahil olmak üzere bir diziye kadar devam edin. Yapı zaten ayrık alt kümelerin başka bir kümesini içeriyorsa, ilgili tüm bilgiler kaybolur. Bu durumda, "RESET DONE" standart çıktısında (ekranında) bir boşlukla ayrılmış iki kelime görüntülenmelidir.
 
JOIN j k — j öğesinin ve k öğesinin ait olduğu alt kümeleri birleştirin. Öğeler zaten aynı alt kümeye aitse, standart çıktıya (ekran) "ZATEN" kelimesini, ardından aynı sırada boşluklarla ayrılmış aynı j ve k rakamlarını yazın. Öğeler şimdiye kadar farklı alt kümelere aitse, işlem yalnızca bellekteki verilerle gerçekleşir, ekranda hiçbir şey görüntülenmez.
 
CHECK j k — j öğesinin ve k öğesinin aynı alt kümeye ait olup olmadığını kontrol edin; standart çıktıya (ekran) "EVET" kelimesini yazdırın; (eğer varsa) veya «NO» (eğer farklıysa).

BREAK - istek almayı durdur.
 
Giriş
Giriş, bir dizi RESET, JOIN ve CHECK sorgusu içerir — her biri, yukarıda açıklanan formata göre ayrı bir satırda. İlk satırın bir RESET sorgusu içermesi ve toplam RESET sorgusu sayısının 5'i geçmemesi garanti edilir. Tüm sorguların toplam sayısı 200000'i geçmez. Her RESET sorgusundaki n değeri 100000'i geçmez. JOIN sorgusu ve her bir KONTROL sorgusunda, her iki sayı da 0 ile n–1 arasında olacaktır; burada n — son yürütülen RESET isteğinin parametresi.
 
Çıktı
RESET, CHECK ve öğelerin zaten aynı altkümeye ait olduğu JOIN sorguları için, karşılık gelen sonucu (ayrı bir satırda) standart çıktıda (ekranda) görüntüleyin.
 
Not
«HAYIR» "CHECK 2 11" istekleri için verilir ve "CHECK 9 1", cevap "ZATEN 4 1" — "JOIN 4 1" isteklerinin ikincisine (10. satır), "EVET" — "5 10 KONTROL ET".
 
 

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++
Giriş Çıktı
15'i SIFIRLA
14 10'A KATILIN
13 8'e KATIL
0 9'a KATIL
8 3'E KATILIN
4 1'e KATIL
10 5'e KATIL
8 4'e KATIL
KONTROL 2 11
4 1'e KATIL
2 6'YA KATILIN
KONTROL 9 1
6 5'e KATIL
KONTROL 10 5
BREAK
SIFIRLA YAPILDI
HAYIR
ZATEN 4 1
HAYIR
EVET
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!