题目描述:
1. A和B是好朋友,则B与A也是好朋友;
2.如果A和C是好朋友,B和C也是好朋友,那么 A和B也是好朋友。
问:现在给出所有好朋友的对数,可以把这些朋友分成多少组,满足每组中的任意两只数码宝贝都是好朋友,且任意两组之间的数码宝贝都不是好朋友。
输入:输入第一行有两个正整数n(小于、等于100),m(小于、等于100),分别表示数码宝贝的个数和好朋友的组数。其中数码宝贝编号为1~n。
接下来有m行每行a,b,表示a与b是好朋友。
输出:输出这些数码宝贝可以分成的组数
1 #include <cstdio>
2 const int maxn = 110;
3 int father[maxn];//存放父亲结点
4 bool isRoot[maxn];//记录每个结点是否作为某个集合的根节点
5
6 void Inint(int n) {
7 for (int i = 1; i <= n; i++) {
8 father[i] = i;
9 isRoot[i] = false;
10 }
11 }
12 int findFather(int x) {
13 int a = x;
14 while (x != father[x]) {
15 x = father[x];
16 }
17
18 //路径压缩,可以不写
19 while (a != father[a]) {
20 int z = a;
21 a = father[a];
22 father[z] = x;
23 }
24 return x;
25 }
26
27 void Union(int a, int b) {//合并a和b所在的集合
28
29 int faA = findFather(a);
30 int faB = findFather(b);
31 if (faA != faB) {
32 father[faA] = faB;
33 }
34 }
35
36 int main() {
37
38 int n, m;
39 scanf("%d%d", &n, &m);
40 int a, b;
41 Inint(n);//初始化
42 for (int i = 0; i < m; i++) {
43 scanf("%d%d", &a, &b);//输入两个好朋友的关系
44 Union(a, b);//合并a和b所在的集合
45 }
46 for (int i = 1; i <= n; i++) {
47 isRoot[findFather(i)] = true;
48 }
49 int ans = 0;//记录集合的数目
50 for (int i = 1; i <= n; i++) {
51 ans += isRoot[i];
52 }
53
54 printf("%d
", ans);
55 return 0;
56 }