2010提高组-C]关押罪犯（扩展域并查集

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+4;
struct node{
    int u,v,w;
}e[M];
int f[M];
bool cmp(node p,node q){
    return p.w>q.w;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=2*n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        int uu=e[i].u+n,vv=e[i].v+n;
        int a=find(u),b=find(v);
        int aa=find(uu),bb=find(vv);
        if(a==b){
            return printf("%dn",e[i].w),0;
        }
        else {
            if(a!=bb)
                f[a]=bb;
            if(aa!=b)
                f[aa]=b;
        }
    }
    printf("0n");
    return 0;
}