題目
連結
題意：在 $10^5 \times 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\n", ans);
62
63 return 0;
64 } 參考連結：https://zhuanlan.zhihu.com/p/72702597
個性簽名：時間會解決一切