题解 | #寻宝#

/**
 简单思路就是：直接用kruskal算法来求最小生成树，最长那一条边就是答案--- kruskal算法天生容易求最长边
                  1. 建立一个类存储顶点a ,顶点b, 权重w，将所有边放直接根据边来排序.
                  2. 搞个并查集。
                  3. 直接对边遍历(排好序从小大的)
                           1. pa = find(a) pb = find(b)直接找a , b的一个祖先
                           2. 如果a , b不在一个连通块即pb != pb ----> p[pa] = pb;放到一个连通块中
                           3. 这个时候你只要简单的 记录最后一条合并的边就好了 也就是最后一个
                                       if(pa != pb){
                                        p[pa] = pb;
                                        max = edges[i].w; //即可
                                   }
     ----------------------------------------没啥说的就是直接kruskal算法-----------------------------------
这里搞个有意思的：
    下面也是我的第一思路，其实我也是写到一半才发现直接kruskal算法就好了，不过还是写下去了
    这个思路是 二分+kruskal
    我第一看到的是  最小值最大，我肯定是想到二分的

    思路
      1. mid = l + r >> 1. 我就拿进去算，对于这个图中所有 w > mid的我就不要了
      2. 如果对于所有 w <= mid的值，你还可以组成一颗最小生成树，那么说明mid 大了 r = mid, 否则说明 mid 小了 l = mid + 1
      3. 接下来就是让他不断二分。找到一个答案就行了

白白浪费时间  我贴的代码就会说二分 + kruskal的 有兴趣的自己改一下，这还是很快的。第二个思路就图一乐吧


*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{


    static int idx, N = 10010, M = 1000010, n, m;
    static Edge[] edges = new Edge[M];
    static int[] p = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = bf.readLine().split(" ");
        n = Integer.parseInt(arr[0]); m = Integer.parseInt(arr[1]);


        for(int i = 0; i < m; i ++){
            String[] brr = bf.readLine().split(" ");
            int a = Integer.parseInt(brr[0]), b = Integer.parseInt(brr[1]), c = Integer.parseInt(brr[2]);
            edges[i] = new Edge(a, b, c);
        }
        Arrays.sort(edges, 0, m, (a, b)->a.w - b.w);


        int l = 0, r = (int)1e9;
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid)) l = mid + 1;
            else r = mid;
        }
        System.out.println(r);
    }

    static boolean check(int mid){
        for(int i = 0; i <= n; i ++)
              p[i] = i;
        int res = 0, sum = 0;
        for(int i = 0; i < m; i ++){
            Edge t = edges[i];
            int a = t.a, b = t.b, w = t.w;
            if(w > mid) continue; // w > mid
            //只有w >= mid的才去计算
            int pa = find(a), pb = find(b);
            if(pa != pb){
                p[pa] = pb;
                res ++;
            }
        }

        if(res == n - 1) return false;
        return true;
    }

    static  class Edge{
        int a, b, w;
        public Edge(int a, int b, int w){
            this.a = a; this.b = b; this.w = w;
        }
    }
    static int find(int x){
        if(p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }


}