小明终于忙完了各种各样的课程，终于可以继续学习算法了。 他在图论书上看到了树，树有许许多多特殊的性质。小明一下子就喜欢上了这种特殊的树。 于是，他发明了自己的对于无向图的评分方法。 一个无向图的分数定义为，各个连通块是树的数量。 现在给定一个n个点m条边的无向图，问在小明的评分方法下，分数为多少。一个连通块是树，当且仅当边数比点数少1。 Input 第一行两个整数n和m，表示图的点数和边数。 第二行有m对整数，u和v表示，结点u和节点v之间有边。给出的无向图不存在重边。 Output 输出一行包括一个整数，表示无向图的评分，也就是树的数量。 Sample Input 8 6 1 2 1 3 2 4 5 6 6 7 5 7 Sample Output 2 HINT 数据范围 20%的数据，1<=n<=2000 100%的数据，1<=n<=100000,0<=m<=min(n*(n-1)/2,200000) 用c++,不要注释，简化变量名

<think>题目要求：计算无向图中树连通块的数量。树连通块的定义是：连通块中边数 = 点数-1。 注意：图可能包含多个连通块，我们需要对每个连通块判断是否满足树的条件（即边数=点数-1）。 思路： 1. 使用并查集或DFS/BFS来找出所有连通块。但是注意，我们需要同时知道每个连通块的点数和边数。 2. 并查集方法：在合并时，我们可以统计每个连通块的点数（用size数组）和边数。但是注意，同一条边在输入中只出现一次，而我们在合并过程中每条边只处理一次。然而，并查集在合并时，我们只能知道合并了两个点，但无法直接知道整个连通块的总边数（因为一个连通块内部可能有多个边，但并查集并不记录所有边）。因此，我们可以考虑： - 方法一：在输入时，对于每条边，我们将其归属到两个点所在的连通块中？但是合并时，边会属于合并后的连通块。然而，并查集在合并时，我们可以为每个连通块维护一个额外的边数。初始时，每个点都是一个连通块，点数为1，边数为0。然后，每加入一条边(u,v)： - 如果u和v不在同一个连通块，那么合并两个连通块，合并后的连通块的点数为两个连通块点数之和，边数为两个连通块边数之和+1（因为当前边加入）。 - 如果u和v在同一个连通块，那么当前边就是该连通块的一条额外边（非树边），那么该连通块的边数加1。 3. 但是这样，我们最后每个连通块的边数就是实际该连通块中的边数吗？ - 注意，在合并过程中，我们每次合并时，对于连接两个不同连通块的边，我们将其边数相加并加1；对于同一连通块内的边，我们直接给该连通块的边数加1。 4. 因此，我们可以用两个数组：parent（父节点）、size（点数）、edges（边数，初始为0）。注意：在合并时，我们将两个连通块的边数相加，然后再加上1（因为当前边连接了两个连通块）。而对于同一连通块内的边，我们只给edges[根]加1。 5. 但是，我们如何保证在合并时，两个连通块的边数都被正确合并？我们只需要在合并时，将两个连通块的边数相加，再加上1（因为当前边）。同时，合并后，新的连通块的边数就是这两个连通块原来的边数之和加1。注意：同一连通块内的边，我们直接加到该连通块的根上。 6. 具体步骤： - 初始化：每个点的父节点是自己，size[i]=1，edges[i]=0（每个连通块初始点数为1，边数为0）。 - 遍历每条边(u,v)（注意：点编号从1开始，我们处理时用0-indexed）： - 找到u和v的根节点ru, rv。 - 如果ru != rv，则合并两个连通块： - 将边数较少的树合并到边数较多的树上（或者按秩合并，这里可以按size合并，也可以不按，因为数据量较大，按size合并可以避免退化）。 - 合并操作：将其中一个根指向另一个根，更新新根的size为两个size之和，更新新根的edges为两个edges之和+1（因为当前边连接了两个连通块，所以这条边属于新连通块）。 - 如果ru == rv，说明u和v已经在同一个连通块，那么当前边就是这个连通块的一条额外边，所以我们将该连通块的边数加1（即edges[ru]++）。 7. 注意：在合并时，我们只更新根节点的信息，非根节点的信息不再使用。 8. 但是，这样处理完后，每个连通块的信息都保存在根节点上。然后我们遍历每个点，如果该点是根节点（即parent[i]==i），那么我们就检查这个连通块：如果连通块的边数 == 连通块的点数-1，那么就是树，计数加1。 9. 但是，我们需要注意：在合并时，我们可能没有处理到所有的边，因为同一连通块内的边我们直接加了，不同连通块之间的边我们合并时加了1。所以这样统计的边数就是该连通块的实际边数。 10. 然而，我们考虑一个连通块的形成：初始时每个点独立，边数为0。然后，当加入一条边连接两个不同连通块时，我们合并，并且边数相加再加1。当加入一条边连接同一个连通块时，我们只给该连通块的边数加1。所以，最终每个连通块的边数就是实际该连通块中的边数。 11. 但是，有一个问题：在合并两个连通块时，我们实际上是将两个连通块的边数相加再加1，这1就是当前这条边。所以，每条边都被计算了一次。因此，正确。 12. 但是，我们需要注意：在合并时，我们可能会改变根节点，所以合并后，原来的根节点可能不再是根节点，所以我们在合并时，需要将两个连通块的根节点信息合并到新的根节点上，并丢弃旧根节点的信息（因为旧根节点不再是根）。 13. 并查集按size合并的代码框架： 初始化： parent[i] = i; size[i] = 1; edges[i] = 0; // 每个连通块初始边数为0 查找根节点（带路径压缩）： int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } 合并： for (每条边(u,v)) { int ru = find(u), rv = find(v); if (ru == rv) { // 同一连通块，边数加1 edges[ru]++; // 注意：这里ru就是根 } else { // 按size合并：将小的树合并到大的树上 if (size[ru] < size[rv]) swap(ru, rv); parent[rv] = ru; size[ru] += size[rv]; edges[ru] += edges[rv] + 1; // 因为当前边也要算上 // 注意：这里我们并没有将rv的size和edges清零，但以后不会再用rv作为根，所以没关系。 } } 14. 但是，这里有一个问题：在合并时，我们只更新了ru的edges，那么rv的连通块的信息就被合并到ru了。然后我们之后遍历所有点，只考虑根节点（即parent[i]==i的点），那么rv就不再是根节点，所以不会重复计算。 15. 最后，我们遍历每个点，如果该点是根节点（parent[i]==i），则判断：edges[i] == size[i]-1 是否成立。如果成立，则树的数量加1。 16. 注意：有可能有孤立点（没有边），那么边数为0，点数1，0==1-1成立，所以孤立点也是树。 17. 但是，我们考虑一个环：比如三个点三条边，那么边数=3，点数=3，3!=3-1，所以不是树。 18. 因此，按照上述方法，我们可以统计出树连通块的数量。 19. 但是，我们需要注意：在合并时，我们只更新了根节点的edges，而同一连通块内的边我们直接加在根节点上。所以，对于每个连通块，边数信息是完整的。 20. 但是，在合并时，如果两个连通块合并，那么原来两个连通块的边数（包括之前合并进来的边）都被加到了新的根节点上，再加上当前这条边，所以正确。 21. 数据范围：n最大100000，m最大200000，所以并查集加路径压缩和按size合并，效率可以接受。 22. 代码步骤： #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100010; int parent[MAXN]; int sz[MAXN]; // size数组，因为size可能和std里的冲突，改用sz int edges[MAXN]; // 记录每个连通块（根节点）的边数 int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } int main() { int n, m; cin >> n >> m; // 初始化 for (int i = 0; i < n; i++) { parent[i] = i; sz[i] = 1; edges[i] = 0; } // 注意：输入的点可能是从1开始编号，所以读入后减1 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; int ru = find(u); int rv = find(v); if (ru == rv) { // 同一连通块，边数加1 edges[ru]++; } else { // 按size合并：将小的树合并到大的树上 if (sz[ru] < sz[rv]) { swap(ru, rv); } parent[rv] = ru; sz[ru] += sz[rv]; edges[ru] += edges[rv] + 1; // 加上rv连通块的边数，再加上当前这条边 } } int ans = 0; for (int i = 0; i < n; i++) { if (parent[i] == i) { // 是根节点 // 判断这个连通块是否是树：边数=点数-1 if (edges[i] == sz[i] - 1) { ans++; } } } cout << ans << endl; return 0; } 23. 但是，这里有一个问题：在合并时，我们使用了路径压缩，但是路径压缩只改变parent指针，不改变size和edges数组（因为我们在合并时已经将信息集中到根节点，路径压缩后非根节点的parent指向根，但非根节点的sz和edges我们并不使用，所以没关系）。 24. 注意：在合并时，我们只更新根节点的sz和edges，非根节点的sz和edges在合并后就不再使用（因为后续查找会路径压缩，但非根节点的sz和edges不会被更新，不过我们只关心根节点的信息，所以没关系）。 25. 但是，在合并两个连通块时，我们可能将rv的根节点指向ru，然后更新ru的sz和edges。这样，rv的sz和edges在合并后就没有更新了（因为rv不再是根节点），所以我们在最后遍历时，只考虑根节点，所以rv的非根节点不会作为根节点被考虑。 26. 因此，上述代码应该是正确的。 27. 但是，我们考虑一个情况：如果两个连通块合并，那么被合并的连通块（rv）的边数信息已经加到ru上，但是rv原来的根节点在后续的边中可能再次出现（作为非根节点），但是我们在find的时候会路径压缩，所以它的parent会指向ru，所以不会再次作为根节点出现。 28. 但是，在合并后，rv的根节点在数组中的edges[rv]和sz[rv]的值并没有被清除，但是我们在遍历时只检查根节点（parent[i]==i），而rv的根节点现在parent[rv]=ru，所以它不再是根节点，因此不会被遍历到。 29. 所以，我们只需要在最后遍历每个点，检查根节点即可。 30. 但是，我们需要注意：在合并时，我们只更新了ru的sz和edges，而rv的sz和edges没有被更新（即rv的根节点的sz和edges还是原来的值，但是我们已经不用了，因为rv不再是根节点）。 31. 因此，代码可以这样写。 32. 但是，我们考虑一下特殊情况：没有边的情况（m=0），那么每个点都是孤立的，所以每个点都是树，因此答案应该是n。 33. 测试一下：输入n=3, m=0，那么初始化三个点，每个点都是根节点，sz=1，edges=0。然后判断每个根节点：0==1-1成立，所以ans=3，正确。 34. 再测试一下样例： Input: 8 6 边：1-2, 1-3, 2-4, 5-6, 6-7, 5-7 连通块1：点1,2,3,4 -> 边数3，点数4 -> 3=4-1 -> 是树。 连通块2：点5,6,7 -> 边数3，点数3 -> 3!=3-1 -> 不是树。 所以树的数量为1？但是样例输出是2。 等等，题目中给出的样例输出是2，为什么？ 重新读题：题目中说“各个连通块是树的数量”。但是，我们上面分析连通块1是树，连通块2不是树，那么应该输出1。 但是，再看样例输入：8个点，6条边，但是只出现了7个点（1到7），还有一个点8（编号为8的点）没有出现！ 所以，实际上有三个连通块： 连通块1：1,2,3,4 -> 边3，点4 -> 是树 连通块2：5,6,7 -> 边3，点3 -> 不是树 连通块3：8 -> 边0，点1 -> 是树 因此，树的数量是2。 所以，我们的代码需要能够处理孤立点（没有边连接的点）。 在我们的初始化中，每个点都是孤立的（即初始时都是根节点，且sz=1，edges=0）。然后，我们只输入了6条边，所以没有涉及的点（比如点8）在并查集中没有被合并，所以它仍然是根节点，并且edges=0，sz=1，满足0=1-1，所以是树。 因此，代码应该输出2。 所以，我们的代码已经考虑了孤立点。 35. 但是，在输入中，我们只读入了m对边，然后处理了m条边。对于没有在边中出现的点，我们不会进行合并操作，所以它们仍然保持初始状态（根节点，sz=1，edges=0），因此会被判定为树。 36. 所以，代码应该正确。 37. 但是，我们考虑一个连通块内有多个环的情况？比如一个连通块有4个点，5条边（即一个环加一条边），那么边数=5，点数=4，5!=4-1，所以不会被计数。正确。 38. 但是，我们考虑一个连通块内有多余的边，但边数恰好等于点数-1？不可能，因为一个连通块如果边数等于点数-1，那么它一定是一棵树（无环且连通）。如果有多余的边，边数就会大于点数-1。 39. 因此，我们只需要判断边数是否等于点数-1。 40. 但是，注意：一个连通块的最小边数应该是点数-1（树），如果小于点数-1，说明不连通？不对，我们这里处理的是连通块，所以连通块内点数至少为1，边数至少为0。而连通块内边数可以小于点数-1吗？不可能，因为连通块的定义是任意两点之间有路径，所以至少需要点数-1条边。但是，我们这里统计的连通块是通过并查集合并的，所以连通块内可能并不连通？不对，并查集保证每个连通块内是连通的。 41. 所以，连通块内边数至少为点数-1（如果少于点数-1，则无法连通）。但是，我们实际统计的边数可能大于等于点数-1。所以，我们只判断是否等于点数-1。 42. 因此，代码正确。 43. 但是，我们考虑一下合并时按秩合并（按size）可能带来的问题：合并顺序不影响连通块的最终点数和边数。因为无论怎么合并，最终连通块的点数都是所有点的和，边数都是所有边的和（包括合并边和同一连通块内的边）。所以正确。 44. 但是，我们上面的合并操作中，对于同一条边，如果它连接两个不同的连通块，我们将其算作1条边加到新的连通块中；如果它连接同一个连通块，我们给该连通块的边数加1。所以，每条边都只被计算了一次。 45. 因此，我们按照上述代码实现。 46. 但是，注意：在合并时，我们更新了ru的edges，但是rv的连通块中可能还有边没有被合并？不会，因为我们在合并时，将rv连通块的所有边（edges[rv]）都加到了ru上，再加上当前这条边（连接两个连通块的边），所以整个连通块的边数就是edges[ru]（更新后）= edges[ru](原)+edges[rv](原)+1。 47. 所以，我们实现了边数的正确合并。 48. 但是，我们考虑一个点：在合并两个连通块时，我们只更新了ru的edges，而rv的edges在合并后就没有用了（因为rv不再是根节点，我们之后不会再用rv的edges）。所以，在合并后，rv的连通块的信息就合并到ru上了。 49. 因此，代码实现如下。 50. 注意：数组大小要开够，n最大100000。 51. 提交代码时，注意不要有注释，变量名简化（但我们已经用了简短的变量名）。 52. 但是，我们上面的代码中，edges数组和sz数组都是每个点一个位置，但实际上只有根节点的信息是有效的。 53. 最后，我们输出ans。 54. 测试样例： 输入：8 6 1 2 1 3 2 4 5 6 6 7 5 7 点0(1),1(2),2(3),3(4),4(5),5(6),6(7),7(8) 注意：点7是8（因为0-indexed，所以点7对应编号8） 处理过程： 初始化：8个点，每个点parent[i]=i, sz[i]=1, edges[i]=0. 第一条边：1-2 -> (0,1) ru = find(0)=0, rv=find(1)=1 -> 不同，合并：假设将1合并到0（因为0的size=1，1的size=1，随便合并） parent[1]=0; sz[0]=2; edges[0] = edges[0]+edges[1]+1 = 0+0+1=1; 第二条边：1-3 -> (0,2) 注意：这里1对应0，3对应2 ru=find(0)=0, rv=find(2)=2 -> 不同，合并 parent[2]=0; sz[0]=3; edges[0]=edges[0]+edges[2]+1=1+0+1=2; 第三条边：2-4 -> (1,3) 注意：2对应1，4对应3 -> 但是1的parent是0，3的parent是3？不对，3还没有被合并。 ru=find(1)=0, rv=find(3)=3 -> 不同，合并 parent[3]=0; sz[0]=4; edges[0]=edges[0]+edges[3]+1=2+0+1=3; 第四条边：5-6 -> (4,5) ru=find(4)=4, rv=find(5)=5 -> 不同，合并 parent[5]=4; sz[4]=2; edges[4]=0+0+1=1; 第五条边：6-7 -> (5,6) 注意：6对应5，7对应6 ru=find(5)=4（因为5的parent是4，然后find(5)会找到4，并且路径压缩后5指向4），rv=find(6)=6 -> 不同，合并 parent[6]=4; sz[4]=3; edges[4]=edges[4]+edges[6]+1=1+0+1=2; 第六条边：5-7 -> (4,6) 注意：5对应4，7对应6 -> 现在4的根是4，6的根是4（因为6的parent=4） ru=find(4)=4, rv=find(6)=4 -> 相同，所以edges[4]++ -> edges[4]变为3。 然后，我们遍历每个点（0~7）： 0: parent[0]=0 -> 连通块：点数=4，边数=3 -> 3==3 -> 是树（因为4-1=3）-> 计数1 1: parent[1]=0 -> 不是根 2: parent[2]=0 -> 不是根 3: parent[3]=0 -> 不是根 4: parent[4]=4 -> 连通块：点数=3，边数=3 -> 3!=2 -> 不是树 5: parent[5]=4 -> 不是根 6: parent[6]=4 -> 不是根 7: parent[7]=7 -> 连通块：点数=1，边数=0 -> 0==0 -> 是树 -> 计数1 所以，ans=2，输出2。符合样例。 55. 因此，我们按照这个思路写代码。 56. 但是，注意：在合并时，我们使用按size合并，所以合并时总是将小的树合并到大树上。这样可以保证树的高度较低，提高效率。 57. 代码实现：</think>```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 100010; int p[N], sz[N], e[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; e[i] = 0; } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; int ru = find(u); int rv = find(v); if (ru == rv) { e[ru]++; } else { if (sz[ru] < sz[rv]) swap(ru, rv); p[rv] = ru; sz[ru] += sz[rv]; e[ru] += e[rv] + 1; } } int ans = 0; for (int i = 0; i < n; i++) { if (p[i] == i) { if (e[i] == sz[i] - 1) { ans++; } } } cout << ans << endl; return 0; } ```