算法1(排序加并查集)$O(n\times logn)$

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define i128 __int128
#define pb push_back
#define all(n) n.begin(),n.end()
#define ppb pop_back
#define eb emplace_back
#define PII pair<int,int> 
#define YES "YES"
#define NO "NO"
#define endl '\n'

using namespace std;
mt19937_64 mrand(random_device{}()); 
const int N = 2e6+10;
int p[N],dis[N];
int find(int x) {
    if(x == p[x] ) return x;
    else {
        int t = p[x];
        p[x] = find(p[x]);
        dis[x] ^= dis[t]; 
        return p[x];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cout.flags(ios::fixed);
    cout.precision(10);
    auto solve = [&](){
        int n,m;
        cin>>n>>m;
        for(int i = 1;i<=n;i++) p[i] = i;
        vector<array<int,3> > a(m);
        for(auto &[x,y,z]:a) cin>>x>>y>>z;
        sort(all(a),[&](array<int,3> a,array<int,3> b){
            return a[2] > b[2];
        });
        int res = 0;
        for(int i = 0;i<m;i++){
            auto [x,y,z] = a[i];
            int px = find(x),py = find(y);
            if(px == py){
                if(dis[x] == dis[y]) res = max(res,z);
            }else {
                p[px] = py;
                dis[px] = dis[x] ^ dis[y] ^ 1;
            }

        }
        // for(int i =1;i<=n;i++) cout<<dsu.find(i)<<" ";
        // cout<<endl;
        cout<<res<<endl;

    };
    int t = 1;
    // cin>>t;
    while(t--) solve();

    return 0;
}

算法2(二分加二分图染色) $O(n \times logn)$

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define i128 __int128
#define pb push_back
#define all(n) n.begin(),n.end()
#define ppb pop_back
#define eb emplace_back
#define PII pair<int,int> 
#define YES "YES"
#define NO "NO"
#define endl '\n'

using namespace std;
mt19937_64 mrand(random_device{}()); 
const int N = 2e6+10;
int p[N],dis[N];
int find(int x) {
    if(x == p[x] ) return x;
    else {
        int t = p[x];
        p[x] = find(p[x]);
        dis[x] ^= dis[t]; 
        return p[x];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cout.flags(ios::fixed);
    cout.precision(10);
    auto solve = [&](){
        int n,m;
        cin>>n>>m;
        for(int i = 1;i<=n;i++) p[i] = i;
        vector<array<int,3> > a(m);
        for(auto &[x,y,z]:a) cin>>x>>y>>z;
        sort(all(a),[&](array<int,3> a,array<int,3> b){
            return a[2] > b[2];
        });
        int l = 0,r = m;
        vector<vector<PII> >g(n+1);
        for(int i = 0;i<m;i++){
            auto [x,y,z] = a[i];
            g[x].pb({y,z});
            g[y].pb({x,z});
        }
        a.pb({0,0,0});

        vector<int> color;
        auto dfs = [&](auto &&dfs,int u,int mid,int tcolor)->bool{
            color[u] = tcolor;
            for(auto [k,v]:g[u]){
                if(v <= mid) continue;
                if(color[k] == -1) {
                    if(!dfs(dfs,k,mid,tcolor^1)) return false;
                }
                else if(color[k] == color[u]) return false;
            }
            return true;
        };
        auto check = [&](int mid){
            color.assign(n+1,-1);
            for(int i = 1;i<=n;i++){
                if(color[i] == -1) {
                    if(!dfs(dfs,i,a[mid][2],0)) return false;
                }
            }
                return true;
        };
        while(l<r){
            int mid = l+r + 1>>1;
            if(check(mid)) l = mid;
            else r = mid-1;
        }
        cout<<a[l][2]<<endl;

    };
    int t = 1;
    // cin>>t;
    while(t--) solve();

    return 0;
}