题目
P1536 村村通
分析
并查集模板题，合并之后扫描 f 数组判断总共几个集合。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std
;
int f
[1005];
int n
, m
;
int getf(int x
)
{
if (f
[x
] == x
)
{
return x
;
}
int fx
= getf(f
[x
]);
return f
[x
] = fx
;
}
void merge(int u
, int v
)
{
int t1
= getf(u
);
int t2
= getf(v
);
if (t1
!= t2
)
{
f
[t1
] = t2
;
}
}
int getAns()
{
int ans
= 0;
for (int i
= 1; i
<= n
; i
++)
{
if (f
[i
] == i
)
{
ans
++;
}
}
return ans
;
}
int main()
{
while (scanf("%d", &n
), n
)
{
scanf("%d", &m
);
memset(f
, 0, sizeof(f
));
for (int i
= 1; i
<= n
; i
++)
{
f
[i
] = i
;
}
for (int i
= 1; i
<= m
; i
++)
{
int u
, v
;
scanf("%d%d", &u
, &v
);
merge(u
, v
);
}
printf("%d\n", getAns() - 1);
}
return 0;
}
