题目链接：戳这里
转自：参考博客
题意：给一个n*m的矩阵，放入q个点，这q个点之间的关系是，若已知这样三个点(x1,y1),(x2,y1),(x1,y2),可以在(x2,y2)处生成一个新的点,对于新的点和被使用过的点都能重复使用,问你最少需要在矩阵汇总添加多少个点是的整个矩阵被点铺满?
解题思路：通过画图可以发现我们对于一个N*M的空矩阵,我们最少填加n+m-1个点就能再通过题意给出的操作不断生成新的点铺满整个图.而且对于题目给出的操作,我们可以发现有这样的规律:
当插入点(x1,y1) 时有关系x1<=>y1
当插入点(x2,y1) 时有关系 x2<=>y1<=>x1
当插入点(x1,y2) 时有关系 y2<=>x1<=>y1<=>x2
我们发现这时候点(x2,y2)很自然的就获得了~
上面的思想可以通过并查集来实现,具体值建立单向边即可,且需要预先对Y坐标进行处理编号为N+1~N+M,剩下的就是判断最少添加多少个关系可以使得所有N+M个坐标关系处于同一集合
附ac代码：
1 #include <iostream> 2 #include <queue> 3 #include <cmath> 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 4e5 + 10; 9 typedef long long ll; 10 int pre[maxn]; 11 void init(int n) 12 { 13 for(int i = 0; i <= n; ++i) 14 pre[i] = i; 15 } 16 int find(int x) 17 { 18 if(pre[x] == x) return x; 19 else return pre[x] = find(pre[x]); 20 } 21 void unit(int x, int y) 22 { 23 x = find(x); 24 y = find(y); 25 if(x == y) return ; 26 else if(x < y) pre[y] = x; 27 else pre[x] = y; 28 } 29 int main() 30 { 31 int n, m, q; 32 scanf("%d %d %d", &n, &m, &q); 33 init(n + m); 34 for(int i = 1; i <= q; ++i) 35 { 36 int u, v; 37 scanf("%d %d", &u, &v); 38 unit(u, v + n); //注意这里是y+n,目的:将纵坐标1~m编号为n+1~n+m 39 } 40 int ans = 0; 41 for(int i = 1; i <= n + m; ++i) 42 { 43 if(find(i) != 1) 44 { 45 ++ans; 46 unit(i, 1);//若是该链是孤立的,将其根直接连到根上(表示为图中增加一个点从而获得连通关系) 47 } 48 } 49 printf("%d ", ans); 50 return 0; 51 }