并查集的高级应用

本文主要是介绍并查集的高级应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1 给定一个 n×m 的矩阵，其中 q 个位置已经被填充。
2 有一条规则，如果 (r1,c1)(r1,c1) ，(r1,c2)(r1,c2)，(r2,c1)(r2,c1) 均被填充，则 (r2,c2)(r2,c2) 也被填充。任何被其他三个位置生成的位置，也可以继续生成其他位置。
问最少需要再人为填充多少元素，使矩阵被填满。
3 The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)),
 the chemical table dimensions and the number of elements scientists already have.
4 
5 The following q lines contain two integers ri, ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m), 
each describes an element that scientists already have. All elements in the input are different.

思路来自这个大佬：

题解
我们考虑自动填充的规则，又三个点自动生成第四个点。如果 (r1,c1)(r1,c1) ，(r1,c2)(r1,c2)，(r2,c1)(r2,c1) 均被填充，则可以看成：

(r1,c1)(r1,c1)：r1r1 和 c1c1 被联系起来
(r1,c2)(r1,c2)：r1r1 和 c2c2 被联系起来
由 1,2→1,2→ c1c1 和 c2c2 被联系起来
(r2,c1)(r2,c1)：r2r2 和 c1c1 被联系起来
由 3,4→3,4→ r2r2 和 c2c2 被联系起来，即有 (r2,c2)(r2,c2) 被填充
这两个模型是等价的。至此，我们把每个边的标号和每个列的标号都看成抽象图中的点，每个给出的点 (r,c)看成一个关于点 r 和点 c 属于同一集合的声明。故我们可以使用并查集维护，计算出当前矩阵中独立集合的数量 NN。

考虑需要人工合并的次数（即认为填充元素的数目）。考虑当前矩阵中未被填充的点，人工填充这个点一定可以实现两个集合的合并，总集合数即减 1。每次人工填充后均自动填充所有可以被自动填充的点。故 N−1 次人工填充后，将全部属于一个集合，矩阵被填满，所以原题的答案即为 N−1。
————————————————
版权声明：本文为CSDN博主「hyp1231」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/hyp1231/article/details/81295464

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 2 * 1e5 + 10;
 6 int p[N * 2];
 7 int n, m, q;
 8 int find(int x)
 9 {
10     if (p[x] != x)
11         p[x] = find(p[x]);
12     return p[x];
13 }
14 int main()
15 {
16     int r, c;
17     scanf("%d%d%d", &n, &m, &q);
18     for (int i=1;i<=n+m;i++) p[i]=i;
19     while (q--)
20     {
21         scanf("%d%d", &r, &c);
22         int fr = find(r), fc = find(c + n);//对于c+n要好好说一番：我们将每一行标上序列 1~n ，为了不重复，我们将每一列从 n+1开始标:
//一直到n+m，正好，m列，对应是n+1~n+m，m个元素。
        if (fr != fc)
24             p[fc] = fr;
25     }
26     int ans = 0;
27     for (int i = 1; i <= n + m; i++)
28     {
29         if (p[i] == i)//当ans为nn时，当nn>=2，从中取两个元素ai,aj，说明（ai,aj）这个点一定是没有的，否则即使p[ai]==ai，但p[aj]应该==ai;
//所以我们要人工加上这个点；当nn<2 ,即nn=1时，这个一定是全部联通，其作为全部的祖父的情况。
30             ans++;
31     }
32     if (ans == 0)
33         printf("%d", ans);
34     else
35         printf("%d", ans - 1);
36     return 0;
37 }

这篇关于并查集的高级应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！