Module: 不相交集系统


Problem

1/9

不相交集系统：开始

Theory Click to read/hide

Problem

编写一个程序，其中将包含以2 种方式（排名启发式和随机）  实现一组不相交集（disjoint sets）的数据结构。  并像这样处理请求：
 
重置 n —创建一个新的子集系列：仅包含元素 0 的集合，仅包含元素 1 的集合，依此类推，直到仅包含元素 n–1 的集合。如果该结构已经包含其他一些不相交的子集，则所有相关信息都将丢失。在这种情况下，标准输出（屏幕）上应显示两个单词“RESET DONE”，中间用空格分隔。
 
加入 j k —合并元素 j 和元素 k 所属的子集。如果元素已经属于同一子集，则将单词“ALREADY”输出到标准输出（屏幕），后跟相同的数字 j 和 k，以空格分隔，顺序相同。如果到目前为止的元素属于不同的子集，那么操作只会对内存中的数据发生，屏幕上不会显示任何内容。
 
检查 j k —检查元素 j 和元素 k 是否属于同一个子集；将单词“YES”输出到标准输出（屏幕）； （如果有的话）或“不”这个词（如果不同的话）。

BREAK - 停止接收请求。
 
输入
输入包含一系列 RESET、JOIN 和 CHECK 查询 —每个单独一行，遵循上述格式。保证第一行包含RESET查询，并且RESET查询的总数不超过5。所有查询的总数不超过200000。每个RESET查询中n的值不超过100000。在每个JOIN 查询和每个 CHECK 查询中，两个数字都在 0 到 n–1 的范围内，其中 n —最后执行的 RESET 请求的参数。
 
输出
对于 RESET、CHECK 和那些元素已经属于同一子集的 JOIN 查询，在标准输出（屏幕）上显示相应的结果（在单独的行中）。
 
注意事项
回答“不”；针对请求“CHECK 2 11”给出和“CHECK 9 1”，答案是“ALREADY 4 1” ——到第二个请求“JOIN 4 1” （第 10 行），“是” ——到“检查 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
打破
重置完成
没有
已经 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!