计算最小生成树中的特定边数

在图论领域，树是一种特殊的图结构，其中任意两节点间恰好存在一条路径。生成树是指从原图中选出部分边，形成一棵包含原图所有顶点的树。而最小生成树（Minimum Spanning Tree, MST）则是在所有可能的生成树中，边的权重之和最小的那一棵。值得注意的是，最小生成树并不总是唯一的。

本题目要求解决的问题是：给定一个没有自环或多重边的加权无向连通图，找出有多少条边至少会出现在其中一个最小生成树中。

输入描述

输入的第一行是一个整数T，代表测试用例的数量。每个测试用例的第一行包含两个整数n和m，分别表示图中的顶点数和边数。接下来的m行，每行包含三个整数a, b, v，表示顶点a与顶点b之间有一条权重为v的边。

输出描述

对于每个测试用例，输出一行，包含一个整数，表示满足条件的边的数量。

样例输入

1
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1

样例输出

4

解题思路

解决此类问题的有效方法之一是使用Kruskal算法。Kruskal算法是一种用于求解最小生成树的经典算法，其基本思想是从图的所有边中按权重从小到大选择边，如果选择的边不会形成环，则将其加入当前的生成树中。为了确保算法正确性，需要特别注意处理具有相同权重的多条边的情况，即在遇到相同权重的边时，动态地判断这些边是否可以作为最小生成树的一部分加入。

具体实现时，首先对所有边按照权重进行排序。然后遍历排序后的边列表，对于每组具有相同权重的边，逐一检查它们是否能被加入当前的生成树中，如果可以，则增加计数器并执行合并操作。这样既保证了算法的效率，也确保了结果的准确性。

代码实现

#include 
#include 
#include 
using namespace std;

int f[100005];
struct Edge {
    int u, v, w;
};
Edge edges[100005];

bool cmp(const Edge &a, const Edge &b) {
    return a.w }

int find(int x) {
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void unionSet(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX != rootY) f[rootY] = rootX;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) f[i] = i;
        for (int i = 0; i             scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
        }
        sort(edges, edges + m, cmp);
        int count = 0;
        for (int i = 0, j; i             for (j = i; j                 if (find(edges[j].u) != find(edges[j].v)) count++;
            }
            for (j = i; j                 if (find(edges[j].u) != find(edges[j].v)) unionSet(edges[j].u, edges[j].v);
            }
        }
        printf("%d\n", count);
    }
    return 0;
}