按照时间排序,
逐个unite。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn=1010; struct edge{ int x,y,t;}a[100010]; int n,m,fa[maxn],cnt; void init(){ for(int i=1;i<=n;i++)fa[i]=i; } int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void unite(int x,int y){ x=find(x);y=find(y); if(x==y)return; cnt--;fa[x]=y; } bool cmp(edge x,edge y){ return x.t<y.t; } int main() { scanf("%d%d",&n,&m);init();cnt=n; for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t); sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++){ unite(a[i].x,a[i].y); if(cnt==1){printf("%d",a[i].t);break;} } if(cnt>1)puts("-1"); return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
转载于:https://www.cnblogs.com/Yzyet/p/7257567.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/10591.html