POJ 1703 Find them, Catch them | 宁心勉学，慎思笃行

最近刷题得进度可以说慢到一定境界上了，今天中午抽空终于把n天前残留的 1703 给过掉了。这个题目也是一个并查集的题目。但是在这道题目中，有一个非常重要的性质：

一个人不是属于集合 A，就是属于集合 B。

这样，假设 A、B 两个人不是在同一个 gang 中，A、C 两个人不是在同一个 gang 中，就必定有 B、C 两个人在同一个 gang 中。因此我们可以放心地将 B、C 两个人合并。

也就是说，每次发现 X Y 在不同的集合中，我们都可以将与 X 不在同一集合的与 Y 合并，将与 Y 不在同一集合的与 X 合并。根据并查集的性质，为了在每次合并时找到与其不在一个集合的元素，我们只需要记录他们的一个代表元素即可，于是我们使用 opt[x] 代表一个与 x 不在同一个集合的元素。

另外，本题读入必须使用 scanf，因为即使取消同步，cin 也会超时。

/* POJ 1703
 * By Ceeji
 * Union
 */
 
#include <iostream>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
#define MAX_N 100000
 
int case_num, n, m;
int parent[MAX_N];
int opt[MAX_N];
 
void init_set ()
{
	for (int i = 0; i < MAX_N; ++i)
		parent[i] = i;
	memset(opt, 0, sizeof(opt));
}
 
int get_parent (int p)
{
	if (parent[p] == p)
		return p;
	parent[p] = get_parent(parent[p]);
	return parent[p];
}
 
void set_union (int x, int y)
{
	int px = get_parent (x);
	int py = get_parent (y);
	if (px == py)
		return;
	parent[px] = py;
}
 
void do_work ()
{
	cin >> n >> m;
	init_set ();
	char c;
	int x, y;
	while (m--)
	{
		scanf("\n%c %d %d", &c, &x, &y);
		//cin >> c >> x >> y;
		if (c == 'D')
		{
			if (opt[x] == 0)
			{
				opt[x] = y;
			}
			else
			{
				set_union (opt[x], y);
			}
			if (opt[y] == 0)
			{
				opt[y] = x;
			}
			else
			{
				set_union (opt[y], x);
			}
		}
		else
		{
			bool finish = false;
			int px = get_parent (x);
			int py = get_parent (y);
			if (px != py)
			{
				if ((opt[x] != 0 && get_parent(opt[x]) == py) || (opt[y] != 0 && get_parent(opt[y]) == px))
					printf("In different gangs.\n");
				else
					printf("Not sure yet.\n");
			}
			else
			{
				printf("In the same gang.\n");
			}
		}
	}
}
 
int main ()
{
	cin >> case_num;
	while (case_num--)
	{
		do_work ();
	}
	return 0;
}

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。

猜你喜欢