并查集
什么是并查集?
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林(parent)，树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
并查集要一般处理的问题
(1)合并:将若干点合并到一个或多个集合(构成一棵树或多棵树)，将多个集合合并(多棵树合并为一颗树);
(2)查询:询问某2个点是否在同一个集合中(查询);
(3）其他:计算共有几个集合（几棵树);
并查集的实现方法
合并的规则是:如果x和y的根相同,则说明在一个集合,不合并.如果x和y的结点不相同,让其中一方的根节点合并到另一方的根上(有时合并需要依据题意,尤其在种类并查集中,本文后面会提到).
查询x和y是否在一个集合? =>查找x和y对应的根,是否是同一个根.
通过一系列的合并操作后,有几个集合,就数有几个根.一般采用数组fa[i] = i来判断.
路径压缩:为了解决多次查询效率不高的问题,例如查询4会依次找到根节点,再查询4,还要重新寻找根节点,所以在查询完后的操作后,不妨直接设该元素的父节点改为根节点.
模板
注意:使用并查集一定要注意初始化,并且正确初始化!
普通并查集
模板:
int find(int x)
{
return fa[x] = fa[x] == x ? x : find(fa[x]);
}
void merger(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy) fa[fx] = fy;
}
主方法:
void slove()
{
cin >> n >> m >> p;//n个数,m个关系,p个查询
for1 (i, n) fa[i] = i;//初始化
for1 (i, m)
{
int x, y;
cin >> x >> y;
merger(x, y);//合并集合
}
for1 (i, p)
{
int x, y;
cin >> x >> y;
//查询集合
if (find(x) == find(y)) cout << "Yes\n";
else cout << "No\n";
}
}
种类并查集
一般的并查集为"亲戚"关系,但是有些是存在"敌对"关系的,这种题型是并查集的一个变种,往往需要开辟1~n之后的数组fa[2*n].而此类问题有一个性质是"敌人的敌人就是朋友"这样的问题.
不妨做一个映射关系,对于一对值x,y.如果他们是敌对关系的话,假设第一个元素的位置值x的敌人是x+n,由于y也是x的敌人,所以第二个元素的位置值y的敌人同样是y+n.那么不难发现,x的朋友是y+n,而y的朋友是x+n.这样就建立了虚拟的朋友.
注意:要把x+n和y+n的父节点设置成真实存在的结点.否则在遍历1~n时,它的父节点都在虚拟节点上,可能会发生错误.
void slove()
{//n个结点,m条关系
cin >> n >> m;
for1 (i, n*2) fa[i] = i;//注意开双倍
for1 (i, m)
{
char c;
int x, y;
cin >> c >> x >> y;
//如果是朋友关系
if (c == 'F') merger(x, y);
else//如果是敌对关系
{//虚拟映射,保证虚拟的父节点为真实结点
merger(x + n, y);
merger(y + n, x);
}
}
int cnt = 0;//如果是根节点+1,得出集合数
for1 (i, n) cnt += fa[i] == i;
cout << cnt;
}
最小生成树
什么是最小生成树
在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树.
应用场景:
例如:要在n企城市之间建设道路，主要日标是要使这 n个城市的任意两个之间都可以通行，但建设道路的费用很高，且各个城市之间建设道路的费用不同，因此另一个目标是要使建设道路的总费用最低。这就需要找到带权的最小生成树。
Kruskal 算法
基本思想:按照权值从小到大的顺序选择n-l条边，并保证这n-l条边不构成回路。e具体做法:首先构造一个只含n全顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
//注意数组的开辟,以及初始化是从1~n不是k
void slove()
{
cin >> n;
for1 (i, n)
{
fa[i] = i;//初始化
for1 (j, n)
{
int t;
cin >> t;
if (i > j)
{
++k;
a[k].x = i;
a[k].y = j;
a[k].z = t;
}
}
}
sort(a + 1, a + 1 + k, cmp);//按照权排序
int sum = 0;//最小和
int cnt = 0;//修的边数
for1 (i, k)
{
int fx = find(a[i].x);
int fy = find(a[i].y);
if (fx != fy)
{
fa[fx] = fy;
++cnt;
sum += a[i].z;
}
if (cnt == n - 1) //结束条件
{
cout << sum;
break;
}
}
}
带权并查集
带权的情况下,需要开辟数组进行维护当前结点到根的权,并用回溯维护正确权.
const int N = 30010;
int p;
int len[N], dis[N];//通过维护长度距离,来维护正确距离
int fa[N];
int find(int x)
{
if (fa[x] == x) return x;
else
{
int t = fa[x];//保存当前结点的父节点
fa[x] = find(fa[x]);//压缩并查找根
//回溯后,更新正确距离
dis[x] = dis[t] + dis[x];
return fa[x];
}
}
void merger(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
fa[fx] = fy;
dis[fx] = dis[fx] + len[fy];
len[fy] = len[fx] + len[fy];
len[fx] = 0;
}
}
void slove()
{
cin >> p;
//初始化
for1 (i, 30000)
{
fa[i] = i;
len[i] = 1;
}
for1 (i, p)
{
char c;
int x;
cin >> c >> x;
if (c == 'M')
{
int y;
cin >> y;
merger(x, y);
}
else
{
find(x);//更新dis距离
cout << dis[x] << endl;
}
}
}
