图的分割
题目大意：
给你n个点，m条边的图，没有重环和自环，所有的点都联通
可以通过删除几条边使得整个图变成两个联通子图
求删除的边中最大边权的最小值
解题思路：
看到“最大边权的最小值”就晓得是经典的二分题目了，所以整体的代码就是二分，现在考虑check()怎么写
（当然边需要经过排序后再去二分）
因为是通过删除几条边而使整个图一分为二，换句话说就是删除边之后的图有两个点集合，那么就可以想到用并查集来维护集合，每次check()时重置集合，将不删除的边连起来，看整个图中有几个集合
代码实现：
#include<bits/stdc++.h>
using namespace std;
// # define int long long
# define endl "\n"
const int N = 1e6+10;
int f[N];
int n,m;
int cnt[N];
struct node{
int a,b,v;
}a[N];
int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
bool check(int mid){
for(int i = 1;i <= n;++i) f[i] = i,cnt[i] = 1;
for(int i = mid+1;i<=m;++i)//删除前mid个边，将后面的边连起来
{
int x = find(a[i].a);
int y = find(a[i].b);
if(x != y){
if(cnt[x]>cnt[y]) swap(x,y);//启发式合并
f[x] = y;
}
}
int cnt = 0;
for(int i = 1;i <= n;++i)//查看图中有几个集合
{
if(f[i] == i) cnt++;
}
return cnt>=2;
}
void solve(){
cin>>n>>m;
for(int i = 1;i <= m;++i){
cin>>a[i].a>>a[i].b>>a[i].v;
}
sort(a+1,a+1+m,[&](node a,node b)->bool{
return a.v<b.v;
});//对边按边权排序
int l = 1,r = m;
int ans = 0;
while(l<=r){
int mid = l+r>>1;
if(check(mid)){
r = mid-1;
ans = mid;
}
else l = mid+1;
}
cout<<a[ans].v<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt;
tt = 1;
// cin>>tt;
while(tt--) solve();
return 0;
}
