Uniqueness of MST

Given any weighted undirected graph, there exists at least one minimum spanning tree (MST) if the graph is connected. Sometimes the MST may not be unique though. Here you are supposed to calculate the minimum total weight of the MST, and also tell if it is unique or not.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (≤ 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by 3 integers:

V1 V2 Weight

where V1 and V2 are the two ends of the edge (the vertices are numbered from 1 to N), and Weight is the positive weight on that edge. It is guaranteed that the total weight of the graph will not exceed 230.

Output Specification:

For each test case, first print in a line the total weight of the minimum spanning tree if there exists one, or else print No MST instead. Then if the MST exists, print in the next line Yes if the tree is unique, or No otherwise. There there is no MST, print the number of connected components instead.

Sample Input 1:

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

Sample Output 1:

11
Yes

Sample Input 2:

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

Sample Output 2:

4
No

Sample Input 3:

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

Sample Output 3:

No MST
2

#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGE_NUM 200000
#define MAX_NODE_NUM 1000
typedef struct
{
    int start, end, weight;
    int isTreeEdge; //判断是否是生成树的一部分
} Edge;

Edge edges[MAX_EDGE_NUM];//倒数第二个测试点一直不行
int n, m, father[MAX_NODE_NUM];

int find_parent(int x)
{
    if (x == father[x]) //如果找到了父节点(节点指向自身)
        return x;
    int a = find_parent(father[x]);
    father[x] = a; //找到之后就直接指向父节点、
    return a;
}

int compareEdges(const void *a, const void *b)
{
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

int main()
{
    scanf("%d %d", &n, &m);//n为总节点数，m为总边数

    for (int i = 0; i < m; ++i)
    {
        scanf("%d %d %d", &edges[i].start, &edges[i].end, &edges[i].weight);
        edges[i].isTreeEdge = 0;
    }
    qsort(edges, m, sizeof(Edge), compareEdges);//使用快排

    for (int i = 1; i <= n; ++i)
        father[i] = i; //初始化为自身

    int total_MST_weight = 0, k_edges = 0, j = 0;
    int flag = 1;

    for (int i = 0; i < m; i = j)
    {
        for (j = i; j < m && edges[j].weight == edges[i].weight; ++j)
            if (find_parent(edges[j].start) != find_parent(edges[j].end))
                edges[j].isTreeEdge = 1;//直接一次性将所有边长相等的边都找出来了

        for (int k = i; k < j; ++k)
        {
            int start = find_parent(edges[k].start), end = find_parent(edges[k].end);
            if (start != end) //若不属于一个集合
            {
                total_MST_weight += edges[k].weight;
                father[start] = end;
                ++k_edges;
            }
            else if (edges[k].isTreeEdge)//start和end属于一个集合，且这条边是将要加入的边中权重相同小的那组
            //所以有多种选择，生成树不唯一
                flag = 0; 
        }
    }

    if (k_edges == n - 1)
        printf("%d\n%s", total_MST_weight, flag ? "Yes" : "No");
    else
        printf("No MST\n%d", n - k_edges); //打印联通分量的个数

    return 0;
}