poj1679 The Unique MST

题目：

Description
Given a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties: 1. V' = V. 2. T is connected and acyclic. Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!

这道题目是让给你一个无向图，让你判断它的最小生成树是否具有唯一性，如果是就输出最小生成树的权值，否则输出"Not Unique!"。
以下是我写的代码和我的个人理解，仅供参考。

参考代码：

#include <iostream>//使用Kruskal算法;
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10000+5;
const int M = 100+5;

int n, m;
int par[M];//保存每个点的根值;//并查集;
int vis[N];//保存访问过的边;
int visnum;//已经访问过多少条边;

struct node {
    int st, ed, cost;
} Points[N];

void init() {
    memset(Points, 0, sizeof(Points));
    for (int i = 1;i < M;++i) {//并查集初始化;
        par[i] = i;
    }
    memset(vis, -1, sizeof(vis));
    visnum = 0;
}

void input() {
    int a, b, c;
    for (int i = 0;i < m;++i) {
        cin >> a >> b >> c;
        Points[i].st = a;
        Points[i].ed = b;
        Points[i].cost = c;
    }
}

bool cmp(const node &a, const node &b) {//按边的权值排序;
    return a.cost < b.cost;
}

int find(int x) {//查询树的根;
    if (par[x] == x) return x;
    else return find(par[x]);
}

void unite(int a, int b) {//合并a和b所属的集合;
    a = find(a);
    b = find(b);
    if (a != b)
        par[a] = b;
}

int mintree() {//求最小生成树;//考虑不连通的情况;
    int res = 0;
    int cnt = 0;
    for (int i = 0;i < m;++i) {
        node e = Points[i];
        int a = find(e.st), b = find(e.ed);//并查集;
        if (a != b) {//a和b不属于同一个集合, 表明该条边没有与其他边构成环;
            unite(e.st, e.ed);
            vis[visnum++] = i;//表明该条边已经被用过;
            res += e.cost;
            ++cnt;
        }
    }
    if (cnt < n - 1) return -1;//根据树的性质;//树的边数=结点数-1;
    return res;
}

int sectree() {//求次小生成树;
    int res = 0;
    int i;
    int minnum = 999999;//寻找次小生成树;
    for (int k = 0;k < visnum;++k) {//保证至少有一条边不是最小生成树的边;
        int cnt = 0;
        res = 0;
        for (int j = 1;j < M;++j) {//初始化并查集;
            par[j] = j;
        }
        for (i = 0;i < m;++i) {
            if (vis[k] != i) {
                node e = Points[i];
                int a = find(e.st), b = find(e.ed);//并查集;
                if (a != b) {
                    unite(e.st, e.ed);
                    res += e.cost;
                    ++cnt;
                }
                //cout << "xyz" << endl;
            }
        }
        if (cnt < n - 1) continue;
        if (vis[k] != i && minnum > res) {//寻找除最小生成树以外的权值最小的树;
            minnum = res;
        }
    }
    return minnum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        if (n == 1) {//特殊情况: 只有1个点;
            cout << 0 << endl;
            continue;
        }
        if (m == 0) {//特殊情况: 没有边;
            cout << "Not Unique!" << endl;
            continue;
        }
        init();
        input();
        sort(Points, Points + m, cmp);//按权值大小排序;
        int ans1 = mintree();
        int ans2 = sectree();
        if (ans1 == ans2 || ans1 == -1) {//若次小生成树的大小不等于最小生成树的大小, 则表明最小生成树是唯一的;
            cout << "Not Unique!" << endl;
        } 
        else cout << ans1 << endl;
    }
    return 0;
}