思路
并查集 + 路径压缩 + 按秩合并(merge: r[x], x的深度)
定义pre[i]为i的根节点(祖先), 先初始化pre[i], 合并各组数据(按秩合并)
最后如果pre[i] = i, 桌子数res ++ (不独立成派, 根节点数即为桌子数)
按秩合并
#include <iostream>
using namespace std;
int t, n, m;
int pre[1010], r[1010];
inline void init(int x)
{
for(int i = 1; i <= x; i ++ )
pre[i] = i;
}
int find(int x)
{
return pre[x] == x ? x : (pre[x] = find(pre[x]));
}
inline void merge(int a, int b)
{
int x = find(a), y = find(b);
if(r[x] <= r[y])
pre[x] = y;
else
pre[y] = x;
if(r[x] == r[y] && x != y)
r[y] ++ ;
}
int main()
{
cin >> t;
while(t -- )
{
cin >> n >> m;
init(n);
int res = 0;
while(m -- )
{
int x, y;
cin >> x >> y;
merge(x, y);
for(int i = 1; i <= n; i ++ )
if(pre[i] == i)
res ++ ;
}
cout << res << endl;
}
return 0;
}