题目
题意：在 $10^5 imes 10^5$ 的大网格上，给出 $n$ 的格点的坐标，求联通块数（上下左右及对角线都认为相邻）
分析
DFS需要遍历网格的每个格点，可能会超时？
初始化时，对每个格点建立并查集，遍历每个格点将相邻的合并，最终的集合个数就是联通块的个数。
具体实现时，对 $n$ 个点的坐标排序，因此合并时只需考虑左上部分。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 5 const int maxn = 1000000 + 10; 6 int fa[maxn]; //fa父节点 7 int mar[maxn]; //记录第i列被覆盖的最大行数对应的下标 8 pair<int, int>p[maxn]; 9 10 //初始化n个节点 11 void init(int n) 12 { 13 for (int i = 1; i <= n; i++) 14 fa[i] = i; 15 } 16 17 //查询树的根 18 int find(int x) 19 { 20 if (x != fa[x]) 21 return fa[x] = find(fa[x]); 22 return fa[x]; 23 } 24 25 //合并x和y所属的集合 26 void unite(int x, int y) 27 { 28 int rx = find(x); 29 int ry = find(y); 30 if (x == y) return; 31 32 fa[rx] = ry; 33 } 34 35 36 int main() 37 { 38 int n; 39 scanf("%d", &n); 40 for(int i = 1;i <= n;i++) scanf("%d%d", &p[i].first, &p[i].second); 41 sort(p+1, p+n+1); //默认就是按第一维排序 42 init(n); 43 for(int i = 1;i <= n;i++) mar[i] = -1; //初始化每列都没有元素 44 45 for(int i = 1;i <= n;i++) 46 { 47 int x = p[i].first, y = p[i].second; 48 if(p[i-1].first == x && p[i-1].second == y-1) unite(i-1, i); //左边 49 50 if(mar[y-1] != -1 && p[mar[y-1]].first == x-1) unite(mar[y-1], i); //左上角 51 52 if(mar[y] != -1 && p[mar[y]].first == x-1) unite(mar[y], i); //上方 53 54 if(mar[y+1] != -1 && p[mar[y+1]].first == x-1) unite(mar[y+1], i); //右上角 55 mar[y] = i; 56 } 57 58 int ans = 0; 59 for(int i = 1;i <= n;i++) 60 if(find(i) == i) ans++; 61 printf("%d ", ans); 62 63 return 0; 64 }