By yusijia

Updated:

Contents 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010

int n , m;
int father[MAXN];/*存储节点的父亲节点*/
int ranks[MAXN];/*存储根节点的儿子节点的个数*/
struct Edge{
   int x;
   int y;
}edge[MAXN];

/*并查集的初始化*/
void init_Set(){
     for(int i = 0 ; i < MAXN ; i++){
        father[i] = i;
        ranks[i] = 1;
     }
}

/*递归查找*/
int Find_Set(int x){
    return x == father[x] ? father[x] : father[x] = Find_Set(father[x]);
}

/*集合的合并*/
void Union(int root_x ,int root_y){
     if(ranks[root_x] > ranks[root_y])
        father[root_y] = root_x;
     else{
        if(ranks[root_x] == ranks[root_y])
            ranks[root_y]++;
        father[root_x] = root_y;
     }
}

void solve(){
     int ans = 0;
     init_Set();/*初始化并查集*/
     for(int i = 0 ; i < m ; i++){
        int root_x = Find_Set(edge[i].x);
        int root_y = Find_Set(edge[i].y);
        if(root_x != root_y){
           ans++;
           Union(root_x , root_y);
        }
     }
     printf("%d\n" , n-1-ans);
}

int main(){
    while(scanf("%d%d" , &n , &m) , n){
        for(int i = 0 ; i < m ; i++)
           scanf("%d%d" , &edge[i].x , &edge[i].y);
        solve();
    }
    return 0;
}
Contents