解题思路:
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int p[N];
int getFather(int x) {
if (x != p[x]) {
p[x] = getFather(p[x]);
}
return p[x];
}
int main()
{
int a, b;
int res = 0;
int m, n, k;
cin >> m >> n >> k;
int total = m * n;
for (int i = 1; i <= total; i++) {
p[i] = i;
}
for (int i = 0; i < k; i++) {
cin >> a >> b;
int fA = getFather(a);
int fB = getFather(b);
if (fA != fB) {
p[fB] = p[fA];
}
}
unordered_set<int> s;
for (int i = 1; i <= total; i++) {
int f = getFather(i);
if (s.count(f) == 0) {
res++;
s.insert(f);
}
}
cout << res << endl;
return 0;
}
0.0分
0 人评分