HDU-6958 KD-Graph

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6 + 10;
int T, n, m, k, fa[maxn], now, ans;
struct da
{
    int u, v, w;
    friend bool operator < (da a, da b) //重载操作符，从小到大排序
    {
        return a.w < b.w;
    }
} q[maxn];

// bool cmp(da aa, da bb) { return aa.w < bb.w; }

int find(int x)
{
    if (fa[x] == x)
        return x;
    fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        now = n; //当前有几个类
        ans = 0;
        //并查集初始化
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        //输入边的左右结点和权值
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &q[i].u, &q[i].v, &q[i].w);
        //将边按照权值排序
        sort(q + 1, q + m + 1);
        for (int i = 1; i <= m; i++)
        {
            if (q[i].w != q[i - 1].w)
            {
                if (now == k)
                {
                    break;
                }
            }
            if (find(q[i].u) == find(q[i].v)) //左右结点属于同一个并查集
                continue;
            fa[find(q[i].u)] = find(q[i].v); //将u，v所属的集合合并为同一并查集
            ans = q[i].w;
            now--; //当前类的个数减一
        }
        printf("%d\n", now == k ? ans : -1);
    }
    return 0;
}