#include
<
iostream
>
#include
<
stdio.h
>
using
namespace
std;
int
sum,n,m;
int
father[
50001
];
void
makeset(
int
x){
for
(
int
i
=
1
;i
<=
x;i
++
) { father[i]
=
i; }}
int
findset(
int
x)
//
查
{
if
(x
!=
father[x]) { father[x]
=
findset(father[x]); }
//
回溯
return
father[x];}
void
Union(
int
a,
int
b){
int
x
=
findset(a);
int
y
=
findset(b);
if
(x
==
y)
return
; sum
=
sum
-
1
; father[y]
=
x;}
int
main(){
int
l; scanf(
"
%d
"
,
&
l);
for
(
int
j
=
1
;j
<=
l;j
++
) { scanf(
"
%d%d
"
,
&
n,
&
m); sum
=
n; makeset(n);
int
first,second;
for
(
int
i
=
1
;i
<=
m;i
++
) { scanf(
"
%d%d
"
,
&
first,
&
second); Union(first,second); } printf(
"
%d\n
"
,sum); getchar(); }
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048236.html
