好朋友 - 并查集

输入格式
输入的第一行有两个正整数n <=100 和m <= 100,分别表示数码宝贝的个数和好朋友的组数,其中数码宝贝的编号为1~n。
接下来有m行,每行两个正整数a和b,表示数码宝贝a和数码宝贝b是好朋友
输出格式
输出一个整数,表示这些数码宝贝可以分成的组数。

样例输入1
4 2
1 4
2 3
样例输出1
2
样例输入2
7 5
1 2
2 3
3 1
1 4
5 6
样例输出2
3

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 "stdio.h"
#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "vector"
//#include "set"
//#include "map"
//#include "stack"
#include "queue"
#include "algorithm"
using namespace std;

//typedef long long LL;
const int maxn= 110;
int father[maxn];//存放父亲结点
bool isRoot[maxn];//记录每个结点是否作为某个集合的根结点
int findFather(int x){//查找x所在集合的根节点
int a = x;
while (x != father[x]) {
x = father[x];
}
//路径压缩
while (a != father[a]) {
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
void Union(int a, int b){//合并a和b所在的集合
int faA = findFather(a);
int faB = findFather(b);
if (faA != faB) {
father[faA] = faB;
}
}
void init(int n){//初始化father[i]为i,且isRoot[i]为false
for (int i = 1; i <= n; i++) {
father[i] = i;
isRoot[i] = false;
}
}
int main(){
int n, m, a, b;
scanf("%d%d", &n, &m);
init(n);
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
Union(a, b);
}
for (int i = 1; i <= n; i++) {
isRoot[findFather(i)] = true;
}
int ans = 0;//记录集合数目
for (int i = 1; i <= n; i++) {
ans += isRoot[i];
}
printf("%d", ans);
return 0;
}