欢迎咨询报名NOIP2019冬令营！<-点击查看

并查集简介

并查集

并查集是一个很高效算法，理解起来也很简单，写起来更简单。

①fat[i] = i;

②找到一个点的祖先

int findfat(int x) { if(fat[x] == x) return x; return findfat(fat[x]); }

③二中的方法肯定不好，因为如果数据比较极端，那么并查集就退化成一个链了

如果加入了路径压缩，并查集这个算法就更高效了。

int findfat(int x)//递归写法 { if(fat[x] == x) return x; fat[x]=findfat(fat[x]); return findfat(fat[x]); } int findfat(int x)//非递归写法 更好，因为不会RE { int root=x; while(root != fat[root])//先要找到根节点r { root=fat[root]; } int y=x; while(y!=root) { int fath=fat[y]; fat[y]=root; y=fath; } return r; }

④合并

void join(int x,int y) { int fatx=findfat(x),faty=findfat(y); if(fatx != faty) { fat[fatx]=faty; } }

带权并查集

带权值的并查集只不过是在并查集中加入了一个value[ ]数组

value[ ]可以记录很多种东西，不一定是类似距离这种东西，也可以是相对于根节点的状态

加入了权值，函数应该有一些改变

①找到一个点的祖先

int findfat(int x) { if(fat[x] == x) return x; int tmp=fat[x]; fat[x]=findfat(fat[x]); //在此处修改val比如： value[x]=value[tmp]+1; return fat[x]; }

以下题目标号来自HDU题库

并查集是一种维护不同集合，在此基础上实现快速判断，统计个数等等的算法。

基础的有find和join两个功能，其中join作用于接收新数据。

并查集应用场景的几个特点：

1.数据之间存在联系；

2.借由两个数据的联系，数据会被双向联通的结合成几个集合；

下面介绍下find和join的基本形式

const int maxn=1000;

int p[maxn];//用于储存数据的根

void init(int n)

{

for(int i=0;i<n;i++)

{

p[i]=i;

}

}

int find(int x)

{

int t=x;

while(p[t]!=t) t=p[t];

int i=x;

while(p[i]!=i)

{

int tem=p[i];

p[i]=t;

i=tem;

}

return t;

}

这种是将关系优化避免出现树变成一条路

还有一种如下

int find(int x)

{

if(p[x]==x)return x;

int tem=find(p[x]);

return tem;

}

这种用递归的方法算

join函数：

void join(int x,int y)

{

int f1=find(x),f2=find(y);

if(f1!=f2)

{

p[f1]=f2;

}

}

知道了这些，一些水题就可以做了

接着是在这个基础上的变化，如统计集合个数，一开始的想法是维护完数据后for一遍，实际这里可以发现，在p[]数组中，作为根节点的数据p[i]==i的，没有必要通过链表结构特点去找根节点。接着处理掉这个for循环：

再看看现在的思路，是通过遍历一遍p[]数组，统计满足p[i]==i的个数，假设为a。如果所有数据没有联通，那么集合个数为n，a=n-（原本p[i]==i的点的p[i]改变的次数），即在join函数中每次寻找到两个数据的根数据进行合并时加一个计数器，然后用n减去。可以这样实现：

int ans=n;

void join(int x,int y)

{

int f1=find(x),f2=find(y);

if(f1!=f2)

{

p[f1]=f2;

ans--;

}

}

接着是找集合中元素个数的题1856，这个可以通过增加一个初始化为1的数组，每次合并同时对应合并，同时max取最大值

#include<iostream>

#include<string>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

#include<map>

const int maxn = 10000005;

#pragma warning(disable:4996)

using namespace std;

// freopen("john.in", "r", stdin);

// freopen("john.out", "w", stdout);

int p[maxn];

int n[maxn];

void pre()

{

for (int i = 1;i < maxn;i++)

{

p[i] = i;

n[i] = 1;

}

}

int find(int x)

{

int r = x;

while (r != p[r])

{

r = p[r];

}

int i = x;

while (i != p[i])

{

int j = p[i];

p[i] = r;

i = j;

}

return r;

}

void join(int x, int y,int& ans)

{

int tem1 = find(x), tem2 = find(y);

if (tem1 != tem2)

{

p[tem1] = tem2;

n[tem2] += n[tem1];

ans = max(n[y], ans);

}

}

int main()

{

int t;

while (~scanf("%d", &t))

{

if (t == 0)puts("1");

else

{

int ans = 0;

pre();

while (t--)

{

int i, j;

scanf("%d%d", &i, &j);

join(i, j, ans);

}

printf("%d\n", ans);

}

}

}

还有一个应用是判断是否成环，如果join的两个数据p[]相同，则标记为成环，如1272这题，还要判断唯一性，可以用前面的方法，也可以通过图论中边数为定点数减一来判断

#include<iostream>

#include<string>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

#include<map>

const int maxn = 100005;

#pragma warning(disable:4996)

using namespace std;

// freopen("john.in", "r", stdin);

// freopen("john.out", "w", stdout);

int p[maxn];

int flag;

bool s[maxn];

int find(int a)

{

while (a != p[a])

{

a = p[a];

}

return a;

}

void join(int a, int b)

{

int i = find(a), j = find(b);

if (i != j)

{

p[i] = p[j];

}

else flag = 0;

}

void pre()

{

for (int i = 1;i < maxn;i++)

{

p[i] = i;

s[i] = false;

}

}

int main()

{

int a, b;

while (cin >> a >> b)

{

if (a == -1 && b == -1)break;

if (a == 0 && b == 0)printf("Yes\n");

else

{

flag = 1;

pre();

s[a] = true;

s[b] = true;

join(a, b);

while (scanf("%d%d", &a, &b), (a || b))

{

s[a] = true;

s[b] = true;

join(a, b);

}

if (flag)

{

int cnt = 0;

for (int i = 1;i < maxn;i++)

{

if (s[i] && p[i] == i)

{

cnt++;

}

if (cnt > 1)

{

flag = 0;

break;

}

}

}

if (flag)printf("Yes\n");

else printf("No\n");

}

}

}

然后是1198这题，这题没有显示的给出数据间的关系，需要对数据进行处理，但并查集的部分没有什么新东西

#include<iostream>

#include<string>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

#include<map>

const int maxn = 550;

#pragma warning(disable:4996)

using namespace std;

// freopen("john.in", "r", stdin);

// freopen("john.out", "w", stdout);

//上下左右分别为0123

int list[11] = { 10,9,6,5,12,3,11,14,7,13,15 };

char a[maxn][maxn];

int ans;

int n, m;

int p[maxn*maxn+1];

void pre(int n)

{

for (int i = 0;i < n;i++)

{

p[i] = i;

}

}

int find(int x)

{

int r = x;

while (r != p[r])

{

r = p[r];

}

return r;

}

void judge(int ai, int aj, int bi, int bj)

{

if (bi >= m || bj >= n)return;

bool flag = false;

int t1 = a[ai][aj] - 'A';

int t2 = a[bi][bj] - 'A';

if (ai == bi&&aj < bj)

{

if (((list[t1] ) & 1) && ((list[t2]>>1) & 1))flag = true;

}

else if (aj == bj&&ai < bi)

{

if(((list[t1] >> 2) & 1) && ((list[t2]>>3) & 1))flag = true;

}

if (flag)

{

int f1 = find(ai*n + aj), f2 = find(bi*n + bj);

if (f1 != f2)

{

p[f1] = f2;

ans--;

}

}

}

int main()

{

//freopen("in.txt", "r", stdin);

while (scanf("%d%d", &m, &n)!= EOF)

{

if (m == -1 || n == -1)break;

pre(m*n);

ans = n*m;

for (int i = 0;i < m;i++)

{

scanf("%s", a[i]);

}

for (int i = 0;i < m;i++)

{

for (int j = 0;j < n;j++)

{

judge(i, j, i, j + 1);

judge(i, j, i + 1, j);

}

}

printf("%d\n", ans);

}

}

然后是现在做的这题，关于带权并查集，还没有弄明白，1829，题意大概是选择动物，给出两个数据的性别相反，问是否出现前后矛盾的情况，上网看到一种解法，思路是开两个数组，每次接收数据，交换p[]中两个数据对应的值，如果有处理到两个数据的p[]相同，则错误。还有一种是带权并查集。做了一个晚上带权那种，还是有点没搞明白。

带权并查集多一个权值的数组，通过递归的find函数找到根节点。现在的问题是，每次找到根节点的过程和合并的过程，会让原本a->b->c的关系变成a->c,b->c每次更新后都要再次调整权值数组。网上的解释是把权值看成向量。例如sign[i]表示由i指向前一个节点的向量，那么改变后的指向由a->c，等于sign[a]+sign[p[a]]。

下面是代码：

#include<iostream>

#include<string>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

#include<map>

#pragma warning(disable:4996)

using namespace std;

// freopen("john.in", "r", stdin);

// freopen("john.out", "w", stdout);

const int maxn = 2002;

int p[maxn];

int sign[maxn];

int find(int x)

{

if (p[x] == x) { return x; }

int tem = p[x];

p[x] = find(p[x]);

sign[x] = (sign[x] + sign[tem]) % 2;//用向量的思想来解释这个过程

return p[x];

}

void unit(int n)

{

for (int i = 1;i <= n;i++)

{

p[i] = i;

sign[i] = 0;

}

}

void join(int x, int y)

{

int f1 = find(x);

int f2 = find(y);

if (f1 != f2)

{

p[f1] = f2;

sign[f1] = (1 + sign[y] - sign[x]) % 2;

}

find(x);

}

int main()

{

freopen("in.txt", "r", stdin);

int t;

scanf("%d", &t);

int cnt = 1;

while (t--)

{

int n, m;

scanf("%d%d", &n, &m);

unit(n);

bool flag = true;

while (m--)

{

int i, j;

scanf("%d%d", &i, &j);

if(flag)join(i, j);

if (sign[i] == sign[j])

{

flag = false;

}

}

printf("Scenario #%d:\n", cnt++);

if (flag)printf("No suspicious bugs found!\n");

else printf("Suspicious bugs found!\n");

printf("\n");

}

}

现在还有个地方没有很清楚，就是在join函数中的sign[f1]的更新，为什么可以直接由sign[x]和sign[y]关系推到？

想通了！在find的过程中已经让x链接到根节点了

今天学习了poj那道经典的食物链，有三个状态，看了结题报告，有两个细微不同的思路，一个是在状态数组sign里存0，1，2代表被吃，同类，吃的关系，另一种是在sign中存三种动物的种类，区别在更新sign数组的表达式上似乎有所不同。

通过这道题，一方面加深了关于向量关系的理解，另一方面是感觉数设的卡诺图化简作为二进制码逻辑关系的化简，这种思路在这种题里意外的有用【捂脸】

#include<iostream>

#include<string>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

#include<map>

#pragma warning(disable:4996)

using namespace std;

// freopen("john.in", "r", stdin);

// freopen("john.out", "w", stdout);

const int maxn = 50002;

int p[maxn];

int sign[maxn];

void init(int n)

{

for (int i = 1;i <= n;i++)

{

p[i] = i;

sign[i] = 0;

}

}

int find(int x)

{

if (x == p[x])return x;

int tem = p[x];

p[x] = find(p[x]);

sign[x] = (sign[x] + sign[tem]) % 3;

return p[x];

}

bool join(int x, int y, int d)

{

int f1 = find(x), f2 = find(y);

if (f1 == f2)

{

if (d == 1 && sign[x] != sign[y])return false;

if (d == 2)

{

if (sign[x] == 2 && sign[y] != 1)return false;

if (sign[x] == 0 && sign[y] != 2)return false;

if (sign[x] == 1 && sign[y] != 0)return false;

}

return true;

}

p[f1] = f2;

if (d == 1)

{

sign[f1] = (sign[y] - sign[x] + 3) % 3;

}

if (d == 2)

{

sign[f1]=(sign[y] - sign[x] + 1 + 3) % 3;

}

find(x);//看看是否必要,可以ac，还是保留吧

return true;

}

int main()

{

// freopen("in.txt", "r", stdin);

int n, k;

scanf("%d%d", &n, &k);

init(n);

int ans = 0;

while (k--)

{

int d, x, y;

scanf("%d%d%d", &d, &x, &y);

if (x > n || y > n)

{

ans++;

continue;

}

if (x == y&&d==2)

{

ans++;

continue;

}

if (!join(x, y, d))ans++;//小心添加错的关系而对正确的关系造成破坏

//判断还是在函数中好，因为在这里会重复做过的事，找到find（x），（y）然后讨论sign[x]sign[y]的关系

}

printf("%d\n", ans);

}

本文例题讲解部分作者roffen，原文链接

欢迎咨询报名NOIP2019冬令营课程！<-点击查看详情

咨询方式：

司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289

定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi