文章目录
- 参考
- 背景
- 思路
- 代码
- 路径压缩
- 按秩合并
参考
- https://blog.csdn.net/the_zed/article/details/105126583
- https://leetcode.cn/problems/redundant-connection/solutions/557616/rong-yu-lian-jie-by-leetcode-solution-pks2/
- https://zhuanlan.zhihu.com/p/93647900
背景
Leetcode 684
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
例题：edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
思路
从图可以看出，1,2,3,4节点形成环，任意一条边都可以是多余边，删除任意一条边都能还原成树。题目说返回最后出现的多余边，那么就是[1,4]了。[1,2], [2,3], [3,4]这三条边使得1节点和4节点已经在一颗树上了(一个集合里)，新增的[1,4]边是多余边。
如何根据过往边快速判断1和4节点在一个集合里呢？用到了并查集。
初始化并查集数组，下标1-5代表节点编号，元素代表节点所属的集合。初始化元素等于节点号，代表此时各个节点各自独立，没有共同集合。因此用5种不同颜色区分。下标0没有实际意义。
[1,2]边，由于1号节点和2号节点不属于一个集合，因此[1,2]边肯定不是多余边，可以将[1,2]边视为树的边。将1号节点和2号节点视为一个集合，因此它们的元素指向同一个节点。
同样[2,3]边也可以视为树的边。因此将2节点和3节点的元素指向3节点。注意：1号节点指向2号节点，不是3节点。但是2号节点指向3号节点。因此通过递归使得1号节点指向3节点，它们属于一个集合。
[3,4]边同理。至此1,2,3,4节点已经属于一个集合，也就是在一颗树上了。
现在处理[1,4]边。由于1节点和4节点属于一棵树，再加上[1,4]边，就变成图了。
代码
class UnionFind {int[] roots; // 并查集数组public UnionFind(int n) {roots = new int[n];for (int i = 0; i < n; i++) {roots[i] = i;}}// 查找当前节点所属集合public int find(int x) {if (x == roots[x]) {return x;}return roots[x] = find(roots[x]); // 这里是路径压缩}// 将两个节点合并到一个集合public void union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {roots[fx] = fy;}}
}
public int[] findRedundantConnection(int[][] edges) {int n = edges.length;UnionFind uf = new UnionFind(n + 1);for (int[] edge : edges) {if (uf.find(edge[0]) == uf.find(edge[1])) {return edge;} else {uf.union(edge[0], edge[1]);}}return null;
}
路径压缩
如图，未压缩路径情况下，每一次计算节点1所属集合都得经历2条边。压缩之后，并查集数组直接记录所属集合。直接获取数组对应元素。
一种路径压缩的思路是每次计算节点所属集合时路径上每个节点的集合。
// 未压缩路径的find()方法，只计算不更新
public int find(int x) {while (x != roots[x]) {x = roots[x];}return x;
}
// 路径压缩
public int find(int x) {if (x == roots[x]) {return x;}return roots[x] = find(roots[x]);
}
路径压缩的原理如图。递归调用栈帧。find(1)方法返回之前将roots[1]=4，实现路径压缩。
路径压缩的问题在于：每次只能压缩单条路径，而且只有使用find()方法时才会进行压缩。
按秩合并
路径压缩处理单条路径。如果遇到两个树合并，可以按秩合并。思想是让树的深度尽量小，做法是将深度小的数合并到深度大的数。如图，合并一个节点和一棵深度为2的树。应该将节点合并到深度更高的数上。
新增数组rank[]记录节点深度(秩)
class UnionFind {int[] roots; // 并查集数组int[] rank; // 秩public UnionFind(int n) {roots = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {roots[i] = i;rank[i] = 1; // 初始化为1，代表深度(秩)未1}}// 查找当前节点所属集合public int find(int x) {if (x == roots[x]) {return x;}return roots[x] = find(roots[x]); // 这里是路径压缩}// 将两个节点合并到一个集合public void union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {if (rank[fx] > rank[fy]) {roots[fy] = fx;} else {if (rank[fx] == rank[fy]) {rank[fy]++;}roots[fx] = fy;}}}
}
