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;
}

猜你喜歡