#include
<
iostream
>
#include
<
stdio.h
>
#include
<
string
.h
>
using
namespace
std;
bool
flags[
1001
];
int
father[
1001
];
void
makeset(
int
n){
for
(
int
i
=
1
;i
<=
n;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
; father[y]
=
x;}
int
main(){
int
n,m;
while
(scanf(
"
%d %d
"
,
&
n,
&
m)
!=
EOF) { memset(flags,
false
,
sizeof
(flags));
if
(n
==
0
)
break
; makeset(n);
int
first,second;
for
(
int
i
=
1
;i
<=
m;i
++
) { scanf(
"
%d %d
"
,
&
first,
&
second); Union(first,second); }
for
(
int
i
=
1
;i
<=
n;i
++
)
//
判断树的棵数
{ flags[findset(i)]
=
true
; }
int
k
=
0
;
for
(
int
i
=
1
;i
<=
n;i
++
) {
if
(flags[i]
==
true
) k
++
; } printf(
"
%d\n
"
,k
-
1
);
//
需要增加的路数等于树的棵树k-1
}
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048238.html
