杭電多校：KD-Graph（并查集）

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
  int u,v;
  ll w;
}e[500010];
bool cmp(node a, node b)
{
  return a.w < b.w;
}
int f[1000010];
int find(int x)
{
  return f[x] == x ? x : f[x]=find(f[x]);
}

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++)f[i] = i;
    for(int i = 1; i <= m; i++)
    {
      scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+1+m,cmp);
    ll ans = 0,cnt = 0;
    cnt = n;
    int flag = 0;
    for(int i = 1; i <= m; i++)
    {
      if(e[i].w != e[i-1].w)
      {
        if(cnt == k)
        {
          flag = 1;
          ans = e[i-1].w;
          break;
        }
      }
      if(find(e[i].u) == find(e[i].v))continue;
      f[find(e[i].u)] = find(e[i].v);
      cnt--;
      
    }
    if(cnt == k)
    {
      cout<<ans<<endl;
    }
    else
    {
      cout<<"-1"<<endl;
    }
  }
}