再次温习并查集的一些思路

算法重温
字数统计: 4.6k字   |   阅读时长: 19分

写在前面

因为之前4月份打了将近一个月的个人赛，有些以前学习过的算法已经忘了，所以重新再温习一遍。

普通并查集

并查集（Union Find）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

对于并查集的理解

首先并查集是一种树型结构，树型结构，顾名思义就是存在着子节点和父节点。

所以我们先设一个数组pre[]，这个数组里面存放每个元素的父节点。然后这里借鉴大佬的例子来解释并查集的作用。

例：话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？

我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物。这样，每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。

但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样，想打一架得先问个几十年，饿都饿死了，受不了。这样一来，队长面子上也挂不住了，不仅效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否是一个帮派的，至于他们是如何通过朋友关系相关联的，以及每个圈子内部的结构是怎样的，甚至队长是谁，都不重要了。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

bcj

下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。
getf这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。

1
2
3
4
5
6
7
int getf(int a)//查找根节点
{
    if (pre[a] == a)//我的上级不是掌门
        return a;
    int tmp = getf(pre[a]);//我就找他的上级，直到掌门出现
    return pre[a] = tmp;//掌门出现
}

再来看看mer函数，就是在两个点之间连一条线，这样一来，原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办，画条线就行了。但我们现在是用并查集来描述武林中的状况的，一共只有一个pre[]数组，该如何实现呢？ 还是举江湖的例子，假设现在武林中的形势如图所示。虚竹帅锅与周芷若MM是我非常喜欢的两个人物，他们的终极boss分别是玄慈方丈和灭绝师太，那明显就是两个阵营了。我不希望他们互相打架，就对他俩说：“你们两位拉拉勾，做好朋友吧。”他们看在我的面子上，同意了。这一同意可非同小可，整个少林和峨眉派的人就不能打架了。这么重大的变化，可如何实现呀，要改动多少地方？其实非常简单，我对玄慈方丈说：“大师，麻烦你把你的上级改为灭绝师太吧。这样一来，两派原先的所有人员的终极boss都是师太，那还打个球啊！反正我们关心的只是连通性，门派内部的结构不要紧的。”玄慈一听肯定火大了：“我靠，凭什么是我变成她手下呀，怎么不反过来？我抗议！”于是，两人相约一战，杀的是天昏地暗，风云为之变色啊，但是啊，这场战争终究会有胜负，胜者为王。弱者就被吞并了。反正谁加入谁效果是一样的，门派就由两个变成一个了。这段函数的意思明白了吧？

1
2
3
4
5
6
7
void mer(int a, int b)//虚竹和周芷若做朋友
{
    int fa = getf(a);//我老大是玄慈
    int fb = getf(b);//我老大是灭绝
    if (fa != fb)
        pre[fa] = fb;//打一仗，谁赢就当对方老大
}

再来看看路径压缩算法。建立门派的过程是用mer函数两个人两个人地连接起来的，谁当谁的手下完全随机。最后的树状结构会变成什么样，我也无法预知，一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门，一共就两级结构，只要找一次就找到掌门了。哪怕不能完全做到，也最好尽量接近。这样就产生了路径压缩算法。
设想这样一个场景：两个互不相识的大侠碰面了，想知道能不能干一场。 于是赶紧打电话问自己的上级：“你是不是掌门？” 上级说：“我不是呀，我的上级是谁谁谁，你问问他看看。” 一路问下去，原来两人的最终boss都是东厂曹公公。 “哎呀呀，原来是自己人，有礼有礼，在下三营六组白面葫芦娃!” “幸会幸会，在下九营十八组仙子狗尾巴花！” 两人高高兴兴地手拉手喝酒去了。 “等等等等，两位大侠请留步，还有事情没完成呢！”我叫住他俩。 “哦，对了，还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长：“组长啊，我查过了，其实偶们的掌门是曹公公。不如偶们一起结拜在曹公公手下吧，省得级别太低，以后查找掌门麻烦。” “唔，有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样，查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理，所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码，看得懂很好，看不懂可以自己模拟一下，很简单的一个递归而已。总之它所实现的功能就是这么个意思。

aa

1
2
int tmp = getf(pre[a]);//路径压缩
    return pre[a] = tmp;

要实现这个例子的代码：

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
40
41
42
43
44
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 10010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx];
int n, m, ans;
void init()
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}
int getf(int a)
{
    if (a == pre[a])
        return a;
    return pre[a] = getf(pre[a]);
}
int mer(int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        ans--;
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m), n)
    {
        init();
        int a, b;
        ans = n - 1;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &a, &b);
            mer(a, b);
        }
        printf("%d\n", ans);
    }
    return 0;
}

带权并查集

就像名字一样，带权并查集就是要多维护一个权值数组;和普通的并查集大同小异,用pre[]数组存父节点，v存当前结点到父亲结点的权值。

首先是初始化：

1
2
3
4
5
6
7
8
void init()
{
    for (int i = 0; i <= n; i++)
    {
        pre[i] = i;
        v[i] = 0;
    }
}

tu

没有进行状态压缩的时候可以知道，pre[3]=2,pre[2]=1,pre[1]=1;v[3]=4;v[2]=3;v[1]=0;

tu

状态压缩后，pre[3]=1;v[3]=7;其他不变;所以可以得出代码如下

1
2
3
4
5
6
7
8
int getf(int a)
{
    if(pre[a]==a)
        return a;
    int tmp=getf(pre[a]);  //这里不能够没有，因为在递归的过程中pre[a]的值会被改变，会影响v[a]的更新
    v[a]=v[a]+v[pre[a]];
    return pre[a]=tmp;
}

而对于合并两个集合，是将元素间关系看成向量
我们可以列出向量图:

tu

我们假设上图中2->1表示1比2大3，同理得其他的，一开始1，2处于一个集合,3,处于另一个集合，现在要将这两个集合合并,那么1->4得权值就可以得出，根据平行四边形法则,v[1]=(-v[2]+v+v[3])=8(其中v表示3比2大多少有，也就是2->3)，就是说4比1大8，由此我们便得到了如何将两个带权集合合并。

1
2
3
4
5
6
7
8
9
10
void mer(int a, int b, int s)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        v[fa] = -v[a] + s + v[b];
    }
}

例题一：HihoCoder-1515

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx], v[maxx];
int n, m, q;
int x, y, s;
int ans;
void init()
{
    for (int i = 0; i <= n; i++)
    {
        pre[i] = i;
        v[i] = 0;
    }
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    v[a] = v[a] + v[pre[a]];
    return pre[a] = tmp;
}
void mer(int a, int b, int s)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        v[fa] = -v[a] + s + v[b];
    }
}
template <class T>
inline void read(T &res) //快速读入模板
{
    char c;
    T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int main()
{
    read(n), read(m), read(q);
    init();
    while (m--)
    {
        read(x), read(y), read(s);
        mer(x, y, s);
    }
    while (q--)
    {
        read(x), read(y);
        if (getf(x) == getf(y))
            printf("%d\n", v[x] - v[y]);
        else
            printf("-1\n");
    }
    return 0;
}

例题二：HDU-3038

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx], v[maxx];
int n, m;
int x, y, s;
void init()
{
    for (int i = 0; i <= n; i++)
    {
        pre[i] = i;
        v[i] = 0;
    }
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    v[a] = v[a] + v[pre[a]];
    return pre[a] = tmp;
}
int mer(int a, int b, int s)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa == fb)
        return v[a] != v[b] + s;
    else
    {
        pre[fa] = fb;
        v[fa] = -v[a] + v[b] + s;
        return 0;
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        init();
        int ans = 0;
        while (m--)
        {
            scanf("%d%d%d", &x, &y, &s);
            y++;
            if (mer(x, y, s))
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

种类并查集

种类并查集，顾名思义，在所给数据中或多或少会带有种类的区别。

种类并查集延用了带权并查集的特性,还是相当于维护了一个权值，只不过这个权值带有一定的意义，拿例题“食物链”来说，我们指定x->y表示与y是x的父节点，即pre[x]=y;我们用rela[i]来表示节点i和它的父节点之间的关系，规定rela[x]=0表示x,y是同类，rela[x]=1表示y吃x，rela[x]=2表示x吃y，那么我们可以根据这些权值推断出两个结点之间实际的关系。

tu

比如现在告诉你3->1的值为1（1吃3），而2->1的值为2（2吃1），那么我们根据题意就可以得出3吃2，即2->3为1,也就得到了上图的关系。假设现在再来一句话说2吃3那么就是错的。问题是如何得到这样的关系。对于给定的x,y和它们之间的关系,我们分两种情况
1.假设pre[x]==pre[y]，就是说它们是一个集合的，现在的任务就是把它们推出它们之间的关系，也就是上图的情况，1为父节点，先开始的条件有3->1的为1,2->1=2，如何得到2->3=1呢？同样我们可以用向量的方法：2->3=2->1 - 1->3(添负号，箭头反向)=2-1=1；这样我们得到了2->3的值为1（这里在想一下，如果我们想得到假设之前我们已经建立了2->1的关系，现在又给出2->1的关系，如何得到到给出的关系对不对呢；我们只需要把上图的3换成1就可以了，同时3->1=1就变成了1->1=0同样的方法）
2.假设pre[x]!=pre[y]，x,y不在同一个集合也就是要联合x,y两个集合,已知y->x=1,x->fx=1,y->fy=0

tu

同样的用向量就可以了fy->fx=-(y->fy)+y->x+x->fx=1+1=2;(已知fx吃x，x吃y，y和fy是同类，所以由题意可知fy吃fx),这样我们就可以将两个集合联合在一起并且维护好关系。
值得注意的是，这些操作对向量方向的要求很高，不能弄错方向，比如联合两个集合的时候,我们求的是fy->fx，也就是fy是儿子，fx是父亲,那么我们就应该pre[fy]=fx；而不是pre[fx]=fy;同样我们求的关系是rela[fy]的值，而不是rela[fx]，如果箭头反向，这些操作都要变.

给出食物链这题的代码(POJ-1182)：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx], rela[maxx];
int n, k;
void init()
{
    for (int i = 0; i <= n; i++)
    {
        pre[i] = i;
        rela[i] = 0;
    }
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    rela[a] = (rela[a] + rela[pre[a]] + 3) % 3;
    return pre[a] = tmp;
}
int mer(int c, int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa == fb)
    {
        if (c == 1 && rela[a] == rela[b])
            return 1;
        else if (c == 2 && (rela[a] - rela[b] + 3) % 3 == c - 1)
            return 1;
        else
            return 0;
    }
    else
    {
        pre[fb] = fa;
        rela[fb] = (-rela[b] + rela[a] - c + 1 + 3) % 3;
        return 1;
    }
}
int main()
{
    scanf("%d%d", &n, &k);
    init();
    int d, x, y;
    int sum = 0;
    while (k--)
    {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n)
            sum++;
        else if (d == 2 && x == y)
            sum++;
        else
        {
            if (!mer(d, x, y))
                sum++;
        }
    }
    printf("%d\n", sum);
    return 0;
}

例题二：POJ-1703

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx * 2];
int n, m;
void init()
{
    for (int i = 0; i <= 2 * n; i++)
    {
        pre[i] = i;
    }
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    return pre[a] = tmp;
}
void mer(int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
        pre[fa] = fb;
}
int same(int a, int b)
{
    return getf(a) == getf(b);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        init();
        char s;
        int a, b;
        while (m--)
        {
            getchar();
            scanf("%c%d%d", &s, &a, &b);
            if (s == 'D')
            {
                mer(a, b + n);
                mer(b, a + n);
            }
            else
            {
                if (same(a, b))
                {
                    printf("In the same gang.\n");
                    continue;
                }
                else if (same(a, b + n))
                {
                    printf("In different gangs.\n");
                }
                else
                {
                    printf("Not sure yet.\n");
                }
            }
        }
    }
    return 0;
}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:再次温习并查集的一些思路

文章作者:Stephencurry6666

发布时间:2020年05月08日 - 15时20分

最后更新:2020年05月11日 - 20时48分

原始链接:https://stephencurry6666.github.io/2020/05/08/%E5%86%8D%E6%AC%A1%E6%B8%A9%E4%B9%A0%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E4%BA%9B%E6%80%9D%E8%B7%AF/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 写在前面
  2. 2. 普通并查集
  3. 3. 带权并查集
  4. 4. 种类并查集
,
字数统计：87.6k 载入天数...载入时分秒...