马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
数据布局与算法学习条记----并查集
@@ author: 明月清了个风
@@ last edited: 2024.11.27
ps：从这里开始参加原题链接了。
Acwing 836. 归并聚集
[原题链接](836. 归并聚集 - AcWing题库)
一共有 n n n个数，编号是 1 ∼ n 1 \sim n 1∼n，最开始每个数各安闲一个聚会集。
现在要举行 m m m个操纵，操纵共有两种：
- M a b，将编号为 a a a和 b b b的两个数所在的聚集归并，假如两个数已经在同一个聚会集，则忽略这个操纵；
- Q a b，扣问编号为 a a a和 b b b的两个数是否在同一个聚会集。
输入格式
第一行输入整数 N N N和 M M M
接下来 m m m行，每行包罗一个操纵指令，指令为M a b或Q a b中的一种。
输特别式
对于每个扣问指令Q a b，都要输出一个结果，假如 a a a和 b b b在同一聚会集，则输出Yes,否则输出No。
每个结果占一行。
数据范围
1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^{5} 1≤n,m≤105,
思绪
起首思索暴力做法，假设维护两个聚集，对于每个聚会集的数维护他所属的聚集标签，当归并时，必要对聚会集的每个数的标签都举行更改，这里时间复杂度是O(N)；对于查询操纵而言，直接对比两个数的标签即可，时间复杂度是O(1).
使用并查集可以将归并和查询操纵的时间复杂度都保持在近似==O(1)==的水平。
并查集是一种用于处置惩罚聚集归并和查询操纵的数据布局，通常用于处置惩罚一些动态连通性标题、图的最小天生树。
通常使用一个数组表现每个元素的父节点，每个聚集都可视为一个树形布局：
- parent表现元素i的父节点。
- 初始时，每个元素的父节点指向自己，即parent = i.
对于其根本操纵查询和归并而言：
- 查找：通过递归和迭代的方式不绝访问父节点，直到找到根节点，也就是parent指向自己的元素。为了优化查询服从，通常使用路径压缩的优化方法，即在查找过程中，将全部访问过的节点直接毗连到根节点，从而淘汰后续查找的路径长度。
- 归并：通常有两种方法，第一种将一个聚集直接毗连到另一个聚集的父节点上；第二种将两个聚集都毗连到一个新父节点上。这里归并时，可以选择将较矮的那棵树链接到较高的树上， 如许可以克制树的高度过高，这是按秩归并的优化方法
代码
- #include <iostream>
- using namespace std;
- const int N = 100010;
- int n, m;
- int p[N];
- int find(int x)
- {
- if(p[x] != x) p[x] = find(p[x]);
- return p[x];
- }
- int main()
- {
- cin >> n >> m;
-
- for(int i = 1; i <= n; i ++) p[i] = i;
-
- while(m --)
- {
- char op[2];
- int a, b;
- cin >> op >> a >> b;
-
- if(op[0] == 'M') p[find(a)] = find(b);
- else
- {
- if(find(a) == find(b)) puts("Yes");
- else puts("No");
- }
- }
-
- return 0;
- }
[原题链接](837. 连通块中点的数量 - AcWing题库)
给定一个包罗 n n n个点（编号为 1 ∼ n 1 \sim n 1∼n）的无向图，初始时图中没有边。
现在要举行 m m m个操纵，操纵共有三种：
- C a b，在点 a a a和点 b b b之间连一条边， a a a和 b b b大概相称。
- Q1 a b，扣问点 a a a和点 b b b是否在同一个连通块中， a a a和 b b b大概相称。
- Q2 a，扣问点 a a a所在连通块中点的数量。
输入格式
第一行输入整数 n n n和 m m m
接下来 m m m行，每行包罗一个操纵指令
输特别式
对于每个扣问指令Q1 a b，假如 a a a和 b b b在同连续通块中，则输出Yes,否则输出No。
于每个扣问指令Q2 a，输出一个整数表现点 a a a所在连通块中点的数量。
每个结果占一行。
数据范围
1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^{5} 1≤n,m≤105,
思绪
- #include <iostream>
- using namespace std;
- const int N = 100010;
- int n, m;
- int cnt[N], p[N];
- int find(int x)
- {
- if(p[x] != x) p[x] = find(p[x]);
- return p[x];
- }
- int main()
- {
- cin >> n >> m;
-
- for(int i = 1; i <= n; i ++) p[i] = i, cnt[i] = 1;
-
- while(m --)
- {
- string op;
- int a, b;
- cin >> op;
- if(op == "C")
- {
- cin >> a >> b;
- a = find(a), b = find(b);
- if(a != b)
- {
- p[a] = b;
- cnt[b] += cnt[a];
- }
- }
- else if(op == "Q1")
- {
- cin >> a >> b;
- if (find(a) == find(b)) puts("Yes");
- else puts("No");
- }
- else
- {
- cin >> a;
- cout << cnt[find(a)] << endl;
- }
- }
-
- return 0;
- }
[原题链接](240. 食品链 - AcWing题库)
动物王国中有三类动物 A , B , C A,B,C A,B,C，这三类动物的食品链构成了风趣的环形
A A A吃 B B B， B B B吃 C C C， C C C吃 A A A。
现有 N N N个动物，以 1 ∼ N 1 \sim N 1∼N编号。
每个动物都是 A , B , C A,B,C A,B,C中的一种，但是我们并不直到它到底是哪一种。
有人用两种说法对这 N N N个动物所构成的食品链关系举行形貌：
第一种说法是1 X Y，表现 X X X和 Y Y Y是同类。
第二种说法是2 X Y，表现 X X X吃 Y Y Y。
此人对 N N N个动物，用上述两种说法，一句接一句地说出 K K K句话。这 K K K句话有的是真的，有的是假的。
但一句话满足下列三条之一时，这句话就是谎言，否则就是实话。
- 当前的话与前面的某些真的话辩说，就是谎言；
- 当前的话中 X X X或 Y Y Y比 N N N大，就是谎言。
- 当前的画表现 X X X吃 X X X，就是谎言。
你的使命是根据给定的 N N N和 K K K句话，输出谎言的总数。
输入格式
第一行是两个整数 N N N和 K K K ，以一个空格分隔。
以下 K K K行每行市三个正整数 D , X , Y D,X, Y D,X,Y，两数之间用一个空格隔开，此中 D D D表现说法的种类。
若 D = 1 D=1 D=1，则表现 X X X和 Y Y Y是同类。
若 D = 2 D=2 D=2，则表现是 X X X 吃 Y Y Y。
输特别式
只有一个整数，表现谎言的数量。
数据范围
1 ≤ N ≤ 50000 1 \leq N \leq 50000 1≤N≤50000,
0 ≤ K ≤ 100000 0 \leq K \leq 100000 0≤K≤100000
思绪
这里用的是y总讲的带权并查集。
并查集的根本操纵是查询和归并，但是在这个过程中可以维护很多信息，好比上一题中聚会集点的个数，这一题中，我们同样可以维护聚会集点之间的关系，由于对一个聚集而言，父节点是雷同的，因此可以根据点与父节点的关系，确定点与点的关系。
起首表明题意
- 第一个谎言条件：当前的话与前面的某些真的话辩说，就是谎言。
比方，已经说过 A A A吃 B B B了，反面又说了 B B B吃 A A A，这就是谎言。
- 第二个谎言条件：当前的话中 X X X或 Y Y Y比 N N N大，就是谎言
比方，给出的 N N N为100，但是说有 101 101 101号动物，就是谎言
- 第三个谎言条件：当前的话表现 X X X吃 X X X，就是谎言
这很好明白。
还要留意的是，当前的话假如判定为真，那么就要对并查集举行维护了。
到这我们已经可以有了根本的代码框架
- int res = 0;
- while(m --) // 挨个读入所有的话
- {
- int t, x, y;
- cin >> t >> x >> y;
- if(x > n || y > n) res ++; // 最简单的第二个条件
- else
- {
- // 另外两种假话条件的判断逻辑
- }
- }
起首不管是第一种还是第二种说法，只有x和y已经在同一个聚会集，也就是之前已经给他们指定过关系之后才会出现谎言，以是起主要找到他们的父节点int px = find(x), py = find(y)并举行判定if(px == py)
针对两种说法中x和y的关系，使用边权办理，通过维护数组d[N]确定。
上面已经说过同一个聚会集的点都根节点有关，因此通过其与根节点的关系，可以确定他们之间的关系，规则界说如下：
- 点到根节点的隔断mod 3 = 1:表现可以吃根节点。
- 点到根节点的隔断mod 3 = 2:表现可以被根节点吃。
- 点到根节点的隔断mod 3 = 0:表现和根节点是同类。
起首看x的边权d[x]的寄义：x到其父节点的隔断，对于每一个点，初始值都为0。这里有个留意点：父节点和根节点的关系。
对于每一个点而言其初始父节点就是自己，根节点也是自己，d[x]初始值自然为1。
但是并查集是通过树形布局存储的，颠末一系列归并操纵后，父节点和所在聚集的根节点就不是一个了，在路径压缩操纵之前，每个点都有两个隔断，一个是到父节点的隔断，一个是到根节点的隔断，但是颠末路径压缩之后，一个点到根节点路径上全部点的父节点都会酿成根节点，因此，颠末路径压缩之后的d[x]才是到聚集根节点的隔断，这也是为什么在这题的路径压缩中，必要额外维护d[x]信息的缘故起因，维护代码如下：
- int find(int x)
- {
- if(p[x] != x)
- {
- int t = find(p[x]);
- d[x] += d[p[x]];
- p[x] = t;
- }
-
- return p[x];
- }
别的两个谎言的判定逻辑
由于我们在探求父节点的时间已经举行了每个点到根节点隔断的更新（也就是点与根节点的关系）。
因此，对于第一种说法1 X Y，当(d[x] - d[y]) % 3 == 0时建立，若不为0则为谎言
对于第二种说法2 X Y,当(d[x] - d[y] - 1) % 3 == 0时建立，若不为0则为谎言，这里表明一下，由于说法二表现 X X X吃 Y Y Y，因此， X X X应被根节点吃d[x] mod 3 == 2，而 Y Y Y吃根节点d[y] mod 3 == 1,如许构成的环形才是 X X X吃 Y Y Y。
代码
- #include <iostream>using namespace std;const int N = 50010;int n, m;int p[N], d[N];int find(int x)
- {
- if(p[x] != x)
- {
- int t = find(p[x]);
- d[x] += d[p[x]];
- p[x] = t;
- }
-
- return p[x];
- }
- int main(){ cin >> n >> m; for(int i = 1; i <= n; i ++) p[i] = i; int res = 0; while(m --) { int t, x, y; cin >> t >> x >> y; if(x > n || y > n) res ++; else { int px = find(x), py = find(y); if(t == 1) { if(px == py && (d[x] - d[y]) % 3) res ++; else if(px != py) { p[px] = p[y]; d[px] = d[y] - d[x]; } } else { if(px == py && (d[x] - d[y] - 1) % 3) res ++; else if(px != py) { p[px] = py; d[px] = d[y] + 1 - d[x]; } } } } printf("%d\n", res); return 0;}
|
发表于 2025-12-19 10:30:06