前言

又被薄纱了捏，发现没有队友啥都做不了捏，发现自己并查集忘光光捏，惨捏，感觉自己好没有用捏，捏，捏……牢骚结束，努力捏_(￣▽￣)*?

并查集

并查集（Disjoint Set）是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。经典应用有连通图、最小生成树Kruskal算法、最近公共祖先(LCA)等。

并查集的基本操作

顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树）
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

初始化

定义一个parent[]， parent[i]是元素i的父亲，开始时，每个元素都是单独的一个节点，也就是说自己是自己的父亲。(✿◕‿◕✿)

int parent[N];void init(int n){    for(int i = 1;i <= n;i ++){        parent[i] = i;    }}

查找

查找元素的集，是一个递归的过程，一层层访问父节点，直到找到根节点（即元素的值和它的集相等）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同。(●’◡’●)

int find(int x){    if(parent[x] == x) return x;    else return find(parent[x]);}

合并

要合并两个集合，我们只需要把一个集合的根节点，连接到另一个集合上ᓚᘏᗢ

void merge(int son,int fa){    parent[find(son)] = parent[find(fa)];}

统计

根据查找我们可以知道，根节点具有“自己的值等于集合的值”这一特性，根据这一特性，我们只要统计出根节点的数量，就可以统计出集合的数量。ヾ(≧▽≦*)o

int calculate(int n){    int ans = 0;    for(int i = 1;i <= n;i ++){        if(parent[i] == i) ans ++;    }    return ans;}

How Many Tables

Problem Description

Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

2
5 3
1 2
2 3
4 5

5 1
2 5

Sample Output

2
4

Author

Ignatius.L

我的代码

#include <bits/stdc++.h>#define int long longconst int N = 1e3 + 5;int parent[N];void init(int n){    for(int i = 1;i <= n;i ++){        parent[i] = i;    }}int find(int x){    if(parent[x] == x) return x;    else return find(parent[x]);}void merge(int son,int fa){    parent[find(son)] = parent[find(fa)];}int calculate(int n){    int ans = 0;    for(int i = 1;i <= n;i ++){        if(parent[i] == i) ans ++;    }    return ans;}void solve(){    int n,m;    std::cin >> n >> m;    init(n);    for(int i = 1;i <= m;i ++){        int son,fa;        std::cin >> son >> fa;        merge(son,fa);    }    std::cout << calculate(n) << '\n';}signed main(){    std::ios::sync_with_stdio(false);    std::cin.tie(0); std::cout.tie(0);    int t;    std::cin >> t;    while (t --){        solve();    }    return 0;}

一个非常基础的并查集的模板题，甚至不需要优化，我就不多叭叭了(☆-ｖ-)

并查集的优化

从前面的知识，我们可以知道，如果这颗搜索树的高度很大的话，复杂度为O(n),变成了一个链表，出现了退化。这时候无论是查找函数，还是合并函数（合并需要用到查找）在极端情况下时间复杂度都为O(n)。

合并的优化

从上面的知识我们可以知道，合并两个集合时，要先搜索到它的根节点，再合并这两个根节点，即把一个根节点的父节点改成另一个根节点。如果把高度较小的集合合并到高度较大的集合就能减少树高

int parent[N];int height[N];void init(int n){    for(int i = 1;i <= n;i ++){        parent[i] = i;        height[i] = 0;    }}int find(int x){    if(parent[x] == x) return x;    else return find(parent[x]);}void merge(int x,int y){    x = find(x);    y = find(y);    if(height[x] = height[y]){        height[x] ++;        parent[y] = x;    } else{        if(height[x] < height[y]){            parent[x] = y;        }else{            parent[y] = x;        }    }}

注：一般不需要合并的优化，我们接下来要说的路径压缩之后，附带优化了合并。

查询的优化（路径压缩）

在上面的给出的查询函数中，查询元素所需要的集，需要搜索路径找到根节点，返回根节点。这条搜索路径可能很长，如果在返回时，把i所属的集改为根节点，那么下次搜索就能在O(1)的时间内得到结果，我们把这个方法叫做：路径压缩

int find(int x){    if(parent[x] != x){        parent[x] = find(parent[x]);     }    return parent[x];}

带权并查集

我们刚刚提到的并查集的主要时用于处理集合关系，每个元素之间只有简单的从属关系，而没有权值。根据我们一开始的引入，我们不难知道，并查集的本质是在维护森林（若干颗树）。并查集的合并和查询优化，实际上是在改变树的形状。我们不妨定义一个权值数组wight[]，把节点i到父节点的权值记为 weight[i]

带权值的路径压缩

原来的权值weight[]，经过压缩之后，更新为 weight[]’，这里我们为了方便说明我们不妨假定 weight[1]’ = weight[1] + weight[2] + weight[3]

 int find(int x){    if(parent[x] != x){        int t = parent[x];        parent[x] = find(parent[x]);        weight[x] += weight[t];    }    return parent[x];}

带权值的合并

在合并操作时，就是把x的根节点合并到y的根节点上，根据题意修改权值

void merge(int x,int y,int v){    int px = find(x);    int py = find(y);    if(px != py){        parent[px] = py;        weight[px] = weight[x] + v;    }}

[NOI2001] 食物链

题目描述

动物王国中有三类动物 $A, B, C$ ，这三类动物的食物链构成了有趣的环形。 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A, B, C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
第二种说法是2 X Y，表示 $X$ 吃 $Y$ 。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；
当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
当前的话表示 $X$ 吃 $X$ ，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

输入格式

第一行两个整数， $N, K$ ，表示有 $N$ 个动物， $K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

100 71 101 12 1 22 2 32 3 31 1 32 3 11 5 5

样例输出 #1

提示

对于全部数据， $1 \leq N \leq 5 \times 10^{4}$ ， $1 \leq K \leq 10^{5}$ 。

我的代码

 #include <bits/stdc++.h>#define int long longconst int N = 5e4 + 5;int parent[N];int val[N];int ans = 0;void init(int n){    ans = 0;    for(int i = 1;i <= n;i ++){        parent[i] = i;        val[i] = 0;    }}int find(int x){    if(parent[x] != x){        int t = parent[x];        parent[x] = find(parent[x]);        val[x] = (val[t] + val[x]) % 3;    }    return parent[x];}void merge(int x,int y,int relate){    int px = find(x);    int py = find(y);    if(px != py){        parent[px] = py;        val[px] = (val[y] - val[x] + relate) % 3;    }}void solve(){    int n,m;    std::cin >> n >> m;    init(n);    for(int i = 1;i <= m;i ++){        int op,x,y;        std::cin >> op >> x >> y;        int px = find(x);        int py = find(y);        if(x > n || y > n){            ans++;            continue;        }        if(op == 1){            if(px == py && (val[x] - val[y] + 3) % 3 != 0){//如果x，y已经在一个集合里面，但是他们的关系不像描述的那样                ans++;                continue;            }else{                merge(x,y,0);            }        }else{            if((px == py && (val[x] - val[y] + 3) % 3 != 1) || x == y){//如果x，y已经在一个集合里面，但是他们的关系不像描述的那样                ans++;                continue;            }else{                merge(x,y,1);            }        }    }    std::cout << ans << "\n";}signed main(){    std::ios::sync_with_stdio(false);    std::cin.tie(0); std::cout.tie(0);    int t = 1;//    std::cin >> t;    while (t --){        solve();    }    return 0;}

题目分析

一开始并没有想到怎么处理权值 ≧ ﹏ ≦ ，看了一下罗老师的思路，感觉非常巧妙

1、我们不妨设一个val[]，来记录i与根节点的关系，0为同类，1为吃，2为被吃

2、我们不妨从初始化开始，画图分析val[]的变化情况

1）一开始A，B，C，D都是独立的个体，相互之间没有关系

2）现在我们知道A -> B(relationship == 1)，所以将val[1]修改成1

3）现在我们又知道B -> C(relationship == 1)，所以将val[2]修改成1，又因为A -> B -> C，所以C -> A，所以将val[1]修改为2

4）同理可得C -> D(relationship == 1)时的情况

3、我们不难发现，合并时（不妨认为将x的根节点接到y的根节点上），x的根节点的val[ ]，更新为(val[y] – val[x] + relationship) % 3。其中val[y] – val[x]为合并后，x的根节点与y的根节点的关系，relationship为x，y之间的关系

Q：好抽象啊，?
A：别急，我们画个图来理解一下

从图上我们不难得到

1）val[D] = val[A] + val[B]’

2）val[D] = x + val[C]

所以有：val[B]’ = val[A] – val[C] + x

4、我们在查询的时候，顺便把叶节点的val，更新为节点到根节点的值

5、最后我们只需要按照题意判断几种说谎的情况就行了

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

博客文章
# 数据结构 # 并查集

学不会的并查集

前言

并查集

并查集的基本操作

初始化

查找

合并

统计

How Many Tables

Problem Description

Input

Output

Sample Input

Sample Output

Author

我的代码

并查集的优化

合并的优化

查询的优化（路径压缩）

带权并查集

带权值的路径压缩

带权值的合并

[NOI2001] 食物链

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

我的代码

题目分析