历届试题 合根植物
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。 这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
Input
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。 接下来一行，一个整数k，表示下面还有k行数据(0<k<100000) 接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。 比如：5 * 4 的小格子，编号： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Output
Examples
样例输入 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 样例输出 5
Hint
题意:
题解:
直接并查集套板子, 然后判断一下根的种类数即可
经验小结:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std
;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL
;
const int inf
= 1<<30;
const LL maxn
= 1e6+10;
int par
[maxn
], rak
[maxn
];
void init(int n
){
for(int i
= 0; i
<= n
; ++i
)
par
[i
] = i
, rak
[i
] = 0;
}
int findr(int x
){
if(x
== par
[x
]) return x
;
else return par
[x
] = findr(par
[x
]);
}
bool isSame(int x
, int y
){return findr(x
)==findr(y
);}
void unite(int x
, int y
){
x
= findr(x
), y
= findr(y
);
if(x
==y
) return;
if(rak
[x
]<rak
[y
]) par
[x
] = y
;
else{
par
[y
] = x
;
if(rak
[x
]==rak
[y
]) ++rak
[x
];
}
}
int main()
{
int m
, n
, k
, a
, b
;
cin
>> m
>> n
>> k
;
init(m
*n
);
for(int i
= 1; i
<= k
; ++i
){
cin
>> a
>> b
;
unite(a
, b
);
}
int ans
= 0;
for(int i
= 1; i
<= m
*n
; ++i
){
if(findr(i
)==i
) ++ans
;
}
cout
<< ans
<< endl
;
return 0;
}
