前言
并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并及查询问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。
操作
- Init：初始化
parent，数组(字典)，保存对应节点所在树的根节点；
rank，数组(字典)，保存对应节点作为根的树的深度，有些特殊情况会有需求；- Union：合并
将两个节点所在的树合并成一棵树，修改rank中树的深度，parent中树的根节点；- Find：查找
通过parent查找元素所在树的根节点。
class UFS {
private int[] parent;
public UFS(int n) {
parent = new int[n + 1];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int xp = find(x), yp = find(y);
if (xp == yp) {
return false;
} else {
parent[xp] = yp;
return true;
}
}
}
684. 冗余连接
public int[] findRedundantConnection(int[][] edges) {
UFS ufs = new UFS(edges.length);
for (int[] edge : edges) {
if (!ufs.union(edge[0], edge[1])) {//如果合并失败，两棵树出现交集，即出现冗余边
return edge;
}
}
return null;
}
685. 冗余连接 II
首先明确树与图的区别，树中不存在入度超过1的节点，也不存在环路(任一枝上都需要存在至少一个出度为0的节点)；由于题目中说明删除的edge应该是最后出现的，所以可以覆盖式记录，根据题意，只存在不超过1个冲突边和环路。
存在3种冗余情况：
- 只存在环路，删除最后出现的环路组成边；
- 只存在入度大于2的冲突边，删除最后出现的冲突边；
- 既存在环路，也存在冲突，删除先出现的冲突边
public int[] findRedundantDirectedConnection(int[][] edges) {
int nodeCount = edges.length;
UFS ufs = new UFS(nodeCount);
HashMap<Integer, Integer> parents = new HashMap<Integer, Integer>();
int conflict = -1, cycle = -1;
for (int i = 0; i < nodeCount; i++) {
if (parents.get(edges[i][1]) != null) {、
//记录入度超过1的节点，如果同时也是闭环边，后面不应该检测出环；
//如果检测出环，另一条冲突边才是环内边，同时解决环和冲突，另一条冲突边是冗余边
conflict = i;
} else {
parents.put(edges[i][1], edges[i][0]);
if (!ufs.union(edges[i][0], edges[i][1])) {
cycle = i;//记录环路节点的闭环边
}
}
}
if (conflict < 0) {
//不存在冲突边，因为必然存在冗余边，所以必然存在环路
return edges[cycle];//返回最后出现的环路边
} else {
//存在入度超过1的节点
if (cycle > 0) {
//存在环路，该冲突边肯定不是环路中的，不然不应该检测出环，所以返回第一条冲突边
return new int[]{parents.get(edges[conflict][1]), edges[conflict][1]};
} else {
//冲突，无环，要么只存在冲突，要么冲突边也存在环内，所以，冲突边是冗余边
return edges[conflict];//返回最后出现的冲突边
}
}
}
