AcWing 4285. 多少张桌子
原题链接
简单
作者:
imnoob
,
2022-02-27 16:16:07
,
所有人可见
,
阅读 301
并查集维护其连通块数量
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int p[N];
int ans;
int find(int n){
if(n != p[n]){
p[n] = find(p[n]);
}
return p[n];
}
void unionset(int xx,int yy){
int x = find(xx), y = find(yy);
if(x != y) ans --;
p[x] = y;
}
void sol(){
int n, m;
cin >> n >> m;
ans = n;
for(int i = 0;i <= n;i ++){
p[i] = i;
}
for(int i = 0;i < m;i ++){
int a, b;
cin >> a >> b;
unionset(a, b);
}
cout << ans << '\n';
}
int main(){
int t;
ios::sync_with_stdio(false);
cin >> t;
while(t --){
sol();
}
}
大佬,能看下我的程序为什么错了吗
哥哥以后刷题能不能写点注释照顾我这种fw
这个其实就是,find函数的目的是找到一个数的祖宗节点,并且将路径上的所有节点都指向他们的祖宗节点;
unionset的目的是,读入的x,y两个数,找到他们所属的集合,将两个集合连接起来;
sol函数的目的是,这个就是读入就不说了;