UVa 11987 Almost Union-Find

想法：

• int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
• vector<int> Set[] : 每個Set裡面可以存放很多數字

分成三個操作：

1. Union：如果x和y不在同個Set，那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set，並同時將Root[]重新指向。例如Set[Root[y]]元素較少，就把Set[Root[y]]內的元素加入到Set[Root[x]]，並且把Set[Root[y]]的元素n，使得Root[n]=Root[x]。
2. Move：如果x和y不在同個Set，就把Set[Root[x]]這個Set內的元素x刪除，並在Set[Root[y]]加入x，記得將Root[x] = Root[y]。
3. Output：輸出Set[Root[x]].size()和該Set內每個元素的和。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int Root[100010];
	vector<int> Set[100010];
	void Set_Initial(int N);
	void Union(int x, int y);
	int main()
	{
	int N, M, Command;
	int x , y;
	while (scanf("%d %d", &N, &M) != EOF) {
	Set_Initial(N);
	while (M--) {
	scanf("%d", &Command);
	if (Command == 1) {
	scanf("%d %d", &x, &y);
	Union(x, y);
	}
	else if (Command == 2) {
	scanf("%d %d", &x, &y);
	if (Root[x] == Root[y]) continue;
	auto iter = Set[Root[x]].begin();
	while (*iter != x) ++iter;
	Set[Root[x]].erase(iter);
	Set[Root[y]].push_back(x);
	Root[x] = Root[y];
	}
	else if (Command == 3) {
	scanf("%d", &x);
	int Sum = 0;
	for (int &n : Set[Root[x]])
	Sum += n;
	printf("%d %d\n", Set[Root[x]].size(), Sum);
	}
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i) {
	Root[i] = i;
	Set[i].clear();
	Set[i].push_back(i);
	}
	}
	void Union(int x, int y)
	{
	x = Root[x];
	y = Root[y];
	if (x == y) return;
	if (Set[x].size() >= Set[y].size()) {
	for (int &n : Set[y]) {
	Set[x].push_back(n);
	Root[n] = x;
	}
	Set[y].clear();
	}
	else {
	for (int &n : Set[x]) {
	Set[y].push_back(n);
	Root[n] = y;
	}
	Set[x].clear();
	}
	}

view raw [UVa] 11987 Almost Union-Find.cpp hosted with ❤ by GitHub