Module: 분리 집합 시스템


Problem

1/9

서로소 집합 시스템: 시작

Theory Click to read/hide

Problem

두 가지 방법(순위 휴리스틱 및 무작위)으로 분리된 세트(disjoint set) 집합에 대한 데이터 구조 구현을 포함하는 프로그램을 작성합니다.   다음과 같은 요청을 처리합니다.
 
RESET n — 요소 0만, 요소 1만 등의 집합에서 n–1 요소만 포함하는 집합까지 일련의 새로운 부분집합을 생성합니다. 구조에 이미 다른 분리된 하위 세트가 포함되어 있으면 모든 관련 정보가 손실됩니다. 이 경우 표준 출력(화면)에 공백으로 구분된 "RESET DONE"이라는 두 단어가 표시되어야 합니다.
 
JOIN j k — 요소 j와 요소 k가 속한 하위 집합을 결합합니다. 요소가 이미 동일한 하위 집합에 속하는 경우 "ALREADY"라는 단어를 표준 출력(화면)에 출력하고 그 뒤에 공백으로 구분된 동일한 숫자 j와 k를 동일한 순서로 출력합니다. 지금까지 요소가 다른 하위 집합에 속했다면 메모리에 있는 데이터에서만 동작이 발생하고 화면에 아무 것도 표시되지 않습니다.
 
체크 j k — 요소 j와 요소 k가 동일한 하위 집합에 속하는지 확인합니다. "YES"라는 단어를 표준 출력(화면)에 출력합니다. (있는 경우) 또는 «NO» (다른 경우).
<사업부>
BREAK - 요청 수신을 중지합니다.
 
입력
입력에는 일련의 RESET, JOIN 및 CHECK 쿼리가 포함됩니다. — 위에서 설명한 형식에 따라 각각 별도의 줄에 표시됩니다. 첫 번째 행이 RESET 쿼리를 포함하고 RESET 쿼리의 총 수가 5를 초과하지 않는 것이 보장됩니다. 모든 쿼리의 총 수는 200000을 초과하지 않습니다. 각 RESET 쿼리의 n 값은 100000을 초과하지 않습니다. JOIN 쿼리 및 각 CHECK 쿼리에서 두 숫자의 범위는 0에서 n–1까지이며 여기서 n — 마지막으로 실행된 RESET 요청의 매개변수입니다.
 
출력
요소가 이미 동일한 하위 집합에 속하는 RESET, CHECK 및 JOIN 쿼리의 경우 해당 결과(별도의 줄)를 표준 출력(화면)에 표시합니다.
 
참고
«NO» "CHECK 2 11" 요청에 대해 제공됩니다. "CHECK 9 1" 답은 "ALREADY 4 1" – 두 번째 요청 "JOIN 4 1" (10번째 줄), "예" – "CHECK 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++
입력 출력
재설정 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
아니요
예
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!