题目

不维护任何信息的并查集

按时间sort一遍，每次合并两个节点，显然如果原先不连通那么合并之后联通块数量–

然后如果n==1就输出当前时间return

在合并的一个思想（我一直没有学会）：
就是对于多个集合
一旦合并一次，集合数就一定会减1
在图那边也适用
当集合数剩1，说明所有都连通了
这个思想一定要会

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+7;
const int M=1e5+7;

int a[N],p[N];
int idx;
int n,m;
typedef pair<int,int>  PII1;
typedef pair<int,PII1>  PII2;
vector<PII2> vec;
int find(int x)
{
    if(p[x]!=x) return find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        p[i]=i;
    }

    for(int i=0;i<=m;i++){
        int x,y,t;scanf("%d%d%d",&x,&y,&t);
        vec.push_back({t,{x,y}});
    }
    sort(vec.begin(),vec.end());
    int sum=n;
    int curt=0;
    for(auto i:vec){
        curt=i.first;
        int x=i.second.first,y=i.second.second;
        if(find(x)!=find(y)){
            p[find(x)]=find(y);
            sum--;
            if(sum==1) break;
        }
    }
    if(sum==1) printf("%d\n",curt);
    else printf("-1");
    return 0;
}