1 #include <cstdio>
2 #include <cstdlib>
3 #include <iostream>
4 #include <algorithm>
5 #include <cstring>
6 using namespace std;
7
8 #define MAXN 5000
9 int fa[MAXN]; //父节点
10 int Rank[MAXN]; //数的高度
11 int ans;
12
13 void init(int n) //初始化
14 {
15 for (int i = 0; i < n; i++)
16 {
17 fa[i] = i; //每个人的根都是自己
18 Rank[i] = 0; //每颗树的高度都为0
19 }
20 }
21
22 int find(int x) //查（查询根节点）
23 {
24 if(fa[x] == x)
25 return x;
26 else
27 {
28 fa[x] = find(fa[x]); //递归求根节点
29 return fa[x];
30 }
31 }
32
33 void set_union(int x, int y) //(并)
34 {
35 x = find(x);
36 y = find(y);
37 if (x == y)
38 return;
39 if (Rank[x] < Rank[y])
40 fa[x] = y;
41 else
42 fa[y] = x;
43 if (Rank[x] == Rank[y])
44 Rank[x]++; //树的高度加一
45 }
46
47 bool same(int x, int y) //判断两个节点是否属于同一个集合
48 {
49 return find(x)==find(y);
50 }
51
52 int main()
53 {
54 int n, m, t;
55 scanf("%d", &t);
56 while (t--)
57 {
58 scanf("%d %d", &n, &m);
59 memset(fa, 0, sizeof(fa));//对父节点进行清零
60 ans = n; //最开始的时候ans = 人数
61 init(n);
62 for (int i = 0; i < m; i++)
63 {
64 int x, y;
65 scanf("%d %d", &x, &y);
66 if (same(x, y))
67 continue;
68 else
69 {
70 set_union(x, y);
71 ans--;
72 }
73 }
74 printf("%d
", ans);
75 }
76 77 return 0;
78 }
