最小生成树+并查集(模板题)
思路
没啥好说的,就是一个模板题,只是与求最小生成树不同的是这题不需要求最小生成树的权值和,只需要求最小生成树中权值最大的那一条边!!!
o.o注意不要把点的数据范围搞成了边的数据范围我就是因为这个卡了半天
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int M=1e5+10;
struct rec
{
int x,y,z;
}edge[M];
int fa[N],ans=INT_MIN,cnt;
int n,m;
bool operator <(rec a,rec b)
{
return a.z<b.z;
}
int get(int x)
{
if(x==fa[x]) return x;
return fa[x]=get(fa[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
edge[i]={x,y,z};
}
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++)
{
int x=get(edge[i].x);
int y=get(edge[i].y);
if(x==y)
continue;
fa[x]=y;
ans=max(ans,edge[i].z);
cnt++;
}
if(cnt==n-1)
cout<<ans<<endl;
else
cout<<-1<<endl;
return 0;
}