POJ 1703 Find them, Catch them 题解 《挑战程序设计竞赛》

POJ 1703 Find them, Catch them

无间道：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。

2.4 加工并储存数据的数据结构

并查集

这题真的很简单，是食物链的弱化版，使用相似的思路来做即可——

定义并查集为：

并查集里的元素i-x表示i属于帮派x

同一个并查集的元素同时成立

可见所有元素个数为2 * N，如果i表示属于帮派A，那么i + N表示属于帮派B，每次输入两个家伙不在同一帮派的时候，就合并他们分属两个帮派的元素。我认为这是最简单最好懂的算法，那些利用复杂节点带权重接着依靠大量if-else维护并查集的做法都不够美。

有个小插曲，这题如果用cin的话会TLE，浪费我不少时间试图优化算法。我还是第一次遇到会让cin TLE的数据量。换用scanf就轻松AC：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

#define MAX_N 100000 * 2 + 16
int parent[MAX_N];
int height[MAX_N];

void init(const int& n)
{
	for (int i = 0; i < n; ++i)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

int find(const int& x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = find(parent[x]);
	}
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
	{
		return;
	}

	if (height[x] < height[y])
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
		if (height[x] == height[y])
		{
			++height[x];
		}
	}
}

bool same(const int& x, const int& y)
{
	return find(x) == find(y);
}


int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		int N, M;
		cin >> N >> M;
		init(N * 2);
		char message;
		int x, y;
		getchar();
		while (M--)
		{
			// cin 会导致TLE，哭笑不得
			// cin >> message >> x >> y;
			scanf("%c%d%d%*c", &message, &x, &y);
 			if (message == 'A')
 			{
 				if (same(x, y))
 				{
 					cout << "In the same gang." << endl;
 				}
 				else if (same(x, y + N))
 				{
 					cout << "In different gangs." << endl;
 				}
 				else
 				{
 					cout << "Not sure yet." << endl;
 				}
 			}
 			else
 			{
 				unite(x, y + N);
 				unite(x + N, y);
 			}
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}

稍微扯远一点，最近看完了《数学之美》这本书，里面提到了最大熵模型，也就是“包含所有可能性”的模型。这道题目其实归根结底就是保留了所有可能性，我们只知道x和y不属于同一集合，但我们不能确定究竟x属于集合A还是集合B，于是我们保留所有可能性，对x-A和x-B都做了一次记录。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1703 Find them, Catch them 题解 《挑战程序设计竞赛》