原题洛谷:https://www.luogu.com.cn/problem/P8654
考点:并查集
套了并查集模板,在join函数中用cnt--记录总集合数量变化最后输出cnt,不知道为什么样例过了最后全WA
#include
#include
#include
using namespace std;
int m,n,k;
int pre[1000005],rankk[1000005]={0},cnt;
int find(int x){
if(pre[x]=x)return x;
return pre[x]=find(pre[x]);
}
void join(int x,int y)
{
x=find(x),y=find(y);
if(x!=y)pre[x]=y;
cnt--;
}
int main(){
cin>>m>>n;
cnt=m*n;
for(int i=1;i<=n*m;i++)pre[i]=i;
int x,y;
cin>>k;
for(int i=0;i>x>>y;
join(x,y);
}
cout<1;
return 0;
}
第10行判断相等写成赋值了;
join函数中,当x==y时,cnt不能减,应该把cnt--写进if里;
最后cnt不要加1。
这是修改后的代码,试过可以通过。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int m, n, k;
int pre[1000005], rankk[1000005] = {0}, cnt;
int find(int x) {
if (pre[x] == x)return x;
return pre[x] = find(pre[x]);
}
void join(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
pre[x] = y;
cnt--;
}
}
int main() {
cin >> m >> n;
cnt = m * n;
for (int i = 1; i <= n * m; i++)pre[i] = i;
int x, y;
cin >> k;
for (int i = 0; i < k; i++) {
cin >> x >> y;
join(x, y);
}
cout << cnt;
return 0;
}
不知道你这个问题是否已经解决, 如果还没有解决的话: