第7周博客，并查集笔记

目录

并查集 (Disjoint-set)

Step 1:

 Step2: 

Step 3: 

 Step 4:

避免最坏情况：

 继续优化：

I - Namesolo 拜师

一：维护生成树

二：按秩合并

证明：

三：路径压缩

---

并查集 (Disjoint-set)

每个集合用一棵“有根树”表示 定义数组 set[1…n] set[i] = i， 则i表示本集合，且是集合对应树的根 set[i] = j，j<>i， 则 j 是 i 的父节点.

int findSet(int x)
{
	if (x == set[x])
		return x;
	else
		return findSet(set[x]);
}
void unionSet(int x, int y)
{
	int fx = findSet(x);
	int fy = findSet(y);
	set[fy] = fx;
}

Step 1: nobody is anybody friend. We have 5 trees and each tree has a single element, which is the root and the representative of that tree.

 Step2: 1 and 2 are friends, unionSet(1, 2) Then we have 4 trees one tree contain 2 elements and have the root 1. The other trees have a single element.

 

Step 3: 5 and 4 are friends, unionSet(5, 4) Now we have 3 trees, 2 trees with 2 elements and one tree with one element.

 Step 4: 5 and 1 are friends, unionSet(1, 5) Now we have 2 trees, one tree has 4 elements and the other one has only one element.

算法复杂度： findSet(x) 最坏O(n) unionSet(x, y) 最坏O(n) 

最坏：

 

避免最坏情况：

启发式合并 方法：将深度小的树合并到深度大的树 实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是: max(h1,h2), if h1<>h2. h1+1, if h1=h2. 效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过lgk

void unionSet(int x, int y)
{
	fx = findset(x);
	fy = findset(y);
	if(rank[fx] > rank[fy])
	{
		set[fy] = fx;
	}
	else
	{
		set[fx] = fy;
		if(rank[fx] == rank[fy])
			rank[fy]++;
	}
}

 继续优化：

路径压缩（Path Compression） 思想：每次查找的时候，把经过路径上的点的父亲都设为根 步骤: 第一步，找到根结点 第二步，修改查找路径上的所有节点，将它们都指向根结点 可以证明m次操作的总时间复杂度为k*O(m)，k是一个接近1的常数，即几乎是线性的。 使用路径压缩的并查集算法不需要再使用启发式合并。

 

 

int findSet(int x)
{
	if (x == set[x])
		return x;
	else
		return set[x] = findSet(set[x]);
}

 

I - Namesolo 拜师

一：维护生成树