题目链接:https://www.luogu.org/problemnew/show/P1536
并查集的运用,可以用生成树的思想,就是n个点生成一棵树需要n-1条边。这样我们先把已有的路连接到一个并查集,并记录数目,最后用n-1减这个数即可。输入n,m时注意一个一个输,这样便于判断n==0
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = ;
int fa[maxn], n, m, tot = , ans[];
struct edge{
int u,v;
}e[];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
int k = ;
while(scanf("%d",&n))
{
if(n == )
{
for(int i = ; i <= k; i++)
printf("%d\n",ans[i]);
return ;
}
scanf("%d",&m);
tot = ;
k++;
for(int i = ; i <= n; i++)
fa[i] = i;
for(int i = ; i <= m; i++)
{
scanf("%d%d",&e[i].u, &e[i].v);
{
int x = find(e[i].u);
int y = find(e[i].v);
if(x!=y)
{
fa[y] = x; tot++;
}
}
}
ans[k] = n - tot -;
} }