Skip to content

1016 Uniqueness of MST

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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 (\le 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 2^{30}.

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

Solution

#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define fi first
#define se second
const int N = 500 * 500 + 10;
int n, m;

struct UFS {
    int fa[N], rk[N];
    void init(int n) {
        memset(fa, 0, sizeof(fa[0]) * (n + 5));
        memset(rk, 0, sizeof(rk[0]) * (n + 5));
    }
    int find(int x) {
        return fa[x] == 0 ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (rk[fx] > rk[fy])
                swap(fx, fy);
            fa[fx] = fy;
            if (rk[fx] == rk[fy])
                ++rk[fy];
            return true;
        }
        return false;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
} ufs;

struct E {
    int u, v, w, use;
    bool operator<(const E &other) const {
        return w < other.w;
    }
} e[N];

void Kruskal() {
    sort(e + 1, e + 1 + m);
    int tot = 0;
    ufs.init(n);
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (ufs.merge(u, v)) {
            e[i].use = 1;
            tot += w;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (ufs.fa[i] == 0) {
            ++cnt;
        }
    }
    if (cnt > 1) {
        printf("No MST\n%d\n", cnt);
        return;
    }
    ufs.init(n);
    int unique = 1;
    for (int i = 1; i <= m; ++i) {
        int j = i;
        for (; j <= m; ++j) {
            if (e[j].w > e[i].w)
                break;
        }
        --j;
        for (int k = i; k <= j; ++k)
            if (e[k].use == 0) {
                int u = e[k].u, v = e[k].v;
                if (!ufs.same(u, v)) {
                    unique = 0;
                    break;
                }
            }
        if (!unique)
            break;
        for (int k = i; k <= j; ++k)
            if (e[k].use) {
                int u = e[k].u, v = e[k].v;
                ufs.merge(u, v);
            }
        i = j;
    }
    printf("%d\n%s\n", tot, unique ? "Yes" : "No");
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        e[i].use = 0;
    }
    Kruskal();
    return 0;
}
Last update: May 4, 2022
Back to top