加工并存储数据的数据结构——《挑战程序设计竞赛》

发表于 | 分类于 | 浏览次数
字数统计: 917 字 | 阅读时长 ≈ 4 分钟

2.4.4 并查集

并查集的实现（交大《数据结构》教材中的实现）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int disjoint[500000]; //使用时别忘了先全部初始化为-1 
int find(int x)
{
	if(disjoint[x] < 0) return x;
	return disjoint[x] = find(disjoint[x]); //路径压缩
}

void Union(int root1, int root2)
{
	if(root1 == root2) return ;
	if(disjoint[root1] > disjoint[root2])// disjoint[root2]为负值，其绝对值为并查集的大小
	{
		disjoint[root2] += disjoint[root1];
		disjoint[root1] =root2;
	}
	else
	{
		disjoint[root1] += disjoint[root2];
		disjoint[root2] =root1;
	}
}

并查集中根节点所存储的数据都为负值，其绝对值为当前根节点这一组中节点的个数。对于n个元素的并查集进行一次操作的复杂度（均摊复杂度）是$O(\alpha(n))$。在这里，$\alpha(n)$是阿克曼(Ackermann)函数的反函数，比$O(\log(n))$还要快。

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
“1 X Y”，表示X和Y是同类。
“2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

起初并不知道每只动物的种类，我想直到所有信息输入完全也很难推断出每只动物是啥种类，所以不妨对每只i创建3个元素i-A, i-B, i-C, 并用这$3\times N$个元素建立并查集，这个并查集维护如下信息：

  • i-x表示“i属于种类x”。
  • 并查集里的每一个组表示组内所有元素代表的情况都同时发生或不发生。

对于每一条信息，只需按照下面进行操作：

  • 第一种，x和y属于同一种类：合并x-A和y-A、x-B和y-B、x-C和y-C。
  • 第二种，x吃y： 合并x-A和y-B、x-B和y-C、x-C和y-A。

在合并之前判断这次合并是否会产生矛盾。例如在第一种信息的情况下，需要检查x-A和y-B或者y-C是否在同一组。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//省略了并查集的实现代码
int N, K; //N种动物，K条信息
int T[MAX_K], X[MAX_K], Y[MAX_K]; //T表示信息的类型
int solve()
{
	int ans = 0;
	for(int i=0;i<K;i++)
	{
		int t = T[i];
		int x = X[i] - 1, y = Y[i] - 1;
		if(x<0 || N<=x || y<0 || N<= y)
		{
			ans++；
			continue;
		}
		if(t==1)
		{
		//x-A和y-B或者y-C是否在同一组，说明已经相信了全面一组信息说，x与y不同类
			if(find(x) == find(y+N) || find(x) == find(y+2*N) ans++;
			else
			{
				Union(x,y);
				Union(x+N,y+N);
				Union(x+2*N,y+2*N);
			}
		}
		else
		{
			if(find(x) == find(y) || find(x) == find(y+2*N) ans++;
			else
			{
				Union(x,y+N);
				Union(x+N,y+2*N);
				Union(x+2*N,y);
			}
		}
	}
	return ans;
}