题目地址：

https://www.lintcode.com/problem/bipartite-graph/description

给定一个$n$阶无向带权完全图，要求求出其中一个二分生成子图，使得两个组中，同一个组里的权值最大的两个点的边最小（这句话的意思是，假设两个组分别是$v_1,...,v_k$，$v_{k+1},...,v_n$，第一组的所有边里权值最大的是$e_1$，第二组的所有边里权值最大的是$e_2$，这里需要让$\max \{e_1,e_2\}$达到最小）。返回$\max \{e_1,e_2\}$。要求这个二分子图的每个组的顶点个数要大于等于$2$。题目保证$n\ge 4$。

为了使得边权尽量的小，我们尝试将边权大的边的两个顶点分配到不同组里。先将所有的边按照长度由大到小排序，然后依次尝试将边加入图中。每次加入的时候，判断一下两个顶点$u$和$v$是否之前已经被分到同一个组里了（因为每次加边的时候实际上会对顶点进行分组，例如，如果加了$(0,1)$这条边，后面又加了$(0,2)$这条边，那么$1$和$2$就自动分到了同一组中），如果两个顶点已经被分到同一个组里了，那么这个边就是答案（如果最优解更小，那么在这个边加完之后就已经不是二分图了，矛盾；如果最优解更大，那么存在二分图能得到一个更小的答案，与解的最优性矛盾），所以输出之；如果之前加的边没有使得这两个点分到同一组，那么就可以对这两个点分别分到两个不同组里去，此时要将所有与$u$不同组的点都与$v$安排到同一组里，并且要将所有与$v$不同组的点都与$u$安排到同一组里。如果此时发现与$u$或者$v$不同组的点的个数已经达到了$n-1$，那么说明这条边就是答案（论证与上面类似）。为了快速判断两个点是否属于同一组，可以用并查集来做。代码如下：

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class Solution { class Edge { int x, y, len; public Edge(int x, int y, int len) { this.x = x; this.y = y; this.len = len; } } class UnionFind { int[] parent; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } public void union(int x, int y) { int px = find(x), py = find(y); if (px == py) { return; } parent[px] = py; } } /** * @param graph: graph edge value * @return: return the minium length of graph */ public int getMiniumValue(int[][] graph) { // write your code here. int n = graph.length; List<Edge> list = new ArrayList<>(); // 初始化所有的边，加入list for (int i = 0; i < n; i++) { int[] edges = graph[i]; for (int j = i + 1; j < edges.length; j++) { list.add(new Edge(i, j, edges[j])); } } // 对边按照边长降序排列 list.sort((e1, e2) -> -Integer.compare(e1.len, e2.len)); // ops[i]存的是与顶点i不同组的顶点编号 List<Set<Integer>> ops = new ArrayList<>(); for (int i = 0; i < n; i++) { ops.add(new HashSet<>()); } UnionFind uf = new UnionFind(n); for (Edge edge : list) { int x = edge.x, y = edge.y; // 如果x和y属于同一组，那么当前边就是答案，将其返回 if (uf.find(x) == uf.find(y)) { return edge.len; } // 将x的”对家点“都与y分到同一组去 if (!ops.get(x).contains(y)) { for (int op : ops.get(x)) { uf.union(op, y); } ops.get(x).add(y); // 如果发现与x对家的点的数量达到了n - 1，那么当前边就是答案，将其返回 if (ops.get(x).size() == n - 1) { return edge.len; } } // 与上同 if (!ops.get(y).contains(x)) { for (int op : ops.get(y)) { uf.union(op, x); } ops.get(y).add(x); if (ops.get(y).size() == n - 1) { return edge.len; } } } // 事实上程序走不到这儿 return 0; } }

时间复杂度$O(E\log E+EV)$，空间$O(E+V^2)$。

注解： 这个题有点像最小生成树的Kruskal算法，也是将边排序，然后一条一条加上去，直到违反某个条件就停止。