先上一波链接qwq https://www.luogu.org/problem/P1111
这题就是裸的并查集咯qwq 维护一下连通块的数目 数目变为一的时候整个图就连通了 输出此时的答案就okay拉
#include<cstdio> #include<cstring> #include<algorithm> const int M=200007; using namespace std; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } struct node{int l,r,T;}e[M]; int cmp(node x,node y){return x.T<y.T;} int n,m,ans=-1,fa[M]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) e[i].l=read(),e[i].r=read(),e[i].T=read(); sort(e+1,e+1+m,cmp); // for(int i=1;i<=m;i++) printf("%d %d %d\n",e[i].l,e[i].r,e[i].T); int cnt=n; for(int i=1;i<=m;i++){ int p=find(e[i].l),q=find(e[i].r); if(p!=q){ cnt--; fa[p]=q; } if(cnt==1){ans=e[i].T; break;} } printf("%d\n",ans); return 0; }