AcWing 4285. 多少张桌子
原题链接
简单
作者:
navystar
,
2023-05-30 09:41:59
,
所有人可见
,
阅读 147
并查集
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;
inline void solve()
{
cin >> n >> m;
for (int i = 0; i <= n; i ++ ) p[i] = i;
function <int (int)> find = [&](int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (int i = 0; i < m; i ++ )
{
int a, b;
cin >> a >> b;
if (find(a) != find(b)) p[find(a)] = find(b);
}
set<int> s;
for (int i = 1; i <= n; i ++ )
if (s.find(find(i)) == s.end()) s.insert(p[i]);
cout << s.size() << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1;
cin >> t;
while (t -- ) solve();
return 0;
}