C++ – 并查集 洛谷 P3367

用于快速查找某个点在哪个集合中,常用于有关图的题中,可查看洛谷P3367题。

#include 
#define _for(i, n) for(int i = 0; i < n; i++)
using namespace std;
const int MAXN = 1e6 + 100;
int m, n, o, x, y;
int map[MAXN];
int find(int u) {
	if(map[u] != u) map[u] = find(map[u]);
	return map[u];
}
int main() {
	scanf("%d %d", &m, &n);
	_for(i, n) map[i] = i;
	_for(i, n) {
		scanf("%d %d %d", &o, &x, &y);
		if(o == 1) map[find(x)] = find(y);
		else if(find(x) == find(y)) printf("Y\n");
		else printf("N\n");
	}
	return 0;
}

以上是并查集的模板代码,也是洛谷的AC代码,其储存结构是map这个一维数组,他存储了不同节点的所在集合,例如map[1] = 1表示节点1是1号集合里的元素,其中find是并查集的主体部分,参数u表示要找节点u所在的集合编号。

首先,我们先从没接触过并查集的角度开始想,我们可以使用节点的编号表示节点所在的集合,例如初始让节点1在1号集合、节点2在2号集合...节点N在N号集合,然后这道题分为两个部分,查找和合并,所以要分为两个角度进行操作,因为查找需要涉及储存方案,所以这里先研究合并,这里的方法是,让一个节点归属到另一个节点之下,例如让节点1与节点2合并,可以让map[1] = 2,,这样节点1与2就同属一个集合了,那么此时还有一个问题如果map[1] = 4、map[2] = 3时该如何操作呢?所以在程序中我们要先find(1)、find(2)然后直接合并他们的归属集合就好了,也就是让map[find(1)] = find(2),最后是查找部分,直接判断find(x)是否等于find(y)然后输出就好了。

然后,如果这么做了,会发现,TLE!

这是因为可能会出现一个问题,就是map[0] = 1、map[1] = 2、 map[2] = 3、 map[3] = 4、 map[4] = 5、 map[5] = 6... map[n - 1] = n,这样就会在查找时耽误很多时间,时间复杂度为O(n),远不如下面这种储存 map[0] = n、map[1] = n、 map[2] = n、 map[3] = n、 map[4] = n、 map[5] = n... map[n - 1] = n, 时间复杂度为O(1),如何实现呢? 就是在find过程中边查找边缩短路径,也就是最上面的代码。

发表回复