[蓝桥杯 2017 国 C] 合根植物
题目描述
w 星球的一个种植园，被分成 m × n m \times n m×n 个小格子（东西方向 m m m 行，南北方向 n n n 列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
第一行，两个整数 m m m， n n n，用空格分开，表示格子的行数、列数（ 1 < m , n < 1000 1<m,n<1000 1<m,n<1000）。
接下来一行，一个整数 k k k，表示下面还有 k k k 行数据 ( 0 < k < 1 0 5 ) (0<k<10^5) (0<k<105)。
接下来 k k k 行，每行两个整数 a a a， b b b，表示编号为 a a a 的小格子和编号为 b b b 的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如： 5 × 4 5 \times 4 5×4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
输出格式
一行一个整数，表示答案
样例 #1
样例输入 #1
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出 #1
5
提示
样例解释
时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
思路
并查集是一种数据结构，主要用于处理一些元素分组问题，可以快速判断两个元素是否属于同一组，也可以快速将两个元素合并到同一组。
首先，读取格子的行数 m m m、列数 n n n 和合根的对数 k k k。然后，初始化并查集，每个元素的父节点都是自己。
接着，读取 k k k 对合根的格子，对于每一对，找到它们的根节点，如果不同则合并。
最后，遍历所有的格子，如果格子的父节点是自己，说明这是一个独立的并查集，即一个合根植物，将答案加一。
AC代码
#include <algorithm>
#include <cmath>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
int m, n, k;
int pre[N];
int root(int x) {
int i = x;
while (i != pre[i]) {
i = pre[i];
}
return i;
}
void merge(int a, int b) {
int ra = root(a);
int rb = root(b);
if (ra == rb) {
return;
}
pre[ra] = rb;
}
int main() {
scanf("%d %d %d", &m, &n, &k);
int mn = m * n;
for (int i = 0; i <= mn; i++) {
pre[i] = i;
}
for (int i = 1; i <= k; i++) {
int a, b;
scanf("%d %d", &a, &b);
merge(a, b);
}
ll ans = 0;
for (int i = 1; i <= mn; i++) {
if (pre[i] == i) {
ans++;
}
}
printf("%lld", ans);
return 0;
}