Leetcode - 261. 以图判树
代码未经过验证，但解题思路是正确的：
class Solution {
/**
* 已知条件1：[a,b]表示连接节点a和节点b的一条无向边，[a,b]和[b,a]表示的是同一条无向边
* 已知条件2：有n个节点，编号为0到(n - 1)；还有一个无向边数组edges，它不包含重复的无向边
* 题目要求：判断这些边是否能够形成一个合法有效的树结构
* 举例说明1：n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]; ret = true
* 举例说明2：n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]; ret = false
*/
//首先，对于n个节点，如果要形成一个有效的树结构，就必须有且仅有(n - 1)条边
//因为边数过少会导致某个节点无法与其它节点连通（也就是说，会有多棵树），过多则会导致环的产生
//如果n个节点正好有(n - 1)条边，那么只要满足下面其中一个条件，即可形成一个有效的树结构：
//1. 从任意一个节点出发，可以到达其余的所有节点
//2. 不存在环（比如[[0,1], [1,2], [0,2]]就存在环）
//这两个条件其实是等价的，我们这里使用第2个条件作为判断的依据
//以n = 5, edges = [[0,1], [2,3], [1,2], [1,3]]为例：
//1. 首先，可以将能够形成一个合法的树的节点放到同一个集合中
// 那么最开始有5个集合，即：[0], [1], [2], [3], [4]
//2. 第一条边是[0,1]，因此将节点0所在的集合与节点1所在的集合合并
// 合并之后变成了4个集合：[0,1], [2], [3], [4]
//3. 第二条边是[2,3]，因此将节点2所在的集合与节点3所在的集合合并
// 合并之后变成了3个集合：[0,1], [2,3], [4]
//4. 第三条边是[1,2]，因此将节点1所在的集合与节点2所在的集合合并
// 合并之后变成了2个集合：[0,1,2,3], [4]
//5. 第四条边是[1,3]，我们发现节点1和节点3已经在同一个集合中了
// 因此添加这条边之后肯定会导致环的产生，无法形成一个有效的树结构，因此返回false
//这里涉及到集合的合并，因此可以使用并查集（不懂的话可以自行了解）；并查集的主要思想是：
//1. 每个集合都选出其中的一个元素来代表该集合，集合内的所有元素（包括代表元素本身）则认这个代表元素为父亲
// 这样的话，只要不断向上找父亲，最终就可以找到某个元素所在集合的代表元素
//2. 将元素i所在的集合与元素j所在的集合合并时，先分别找到i和j所在集合的代表元素，假设它们分别是a和b
// 如果a和b相等，说明i和j已经在同一个集合中了，此时再进行合并，则会导致环的产生
// 如果a和b不相等，则将a指定为b的父亲，或将b指定为a的父亲（也可以采用优化方案：按秩合并）
public boolean validTree(int n, int[][] edges){
if(edges.length != n - 1)
return false;
UnionFindSets ufs = new UnionFindSets(n);
for(int[] edge : edges){
//将edge[0]所在集合与edge[1]所在集合进行合并
//如果合并失败，说明出现了环，此时直接返回false
if(!ufs.union(edge[0], edge[1]))
return false;
}
//执行到这里，说明确实可以形成一棵树
assert(ufs.getGroupCount() == 1);
return true;
}
}
/**
* 一个简单的并查集
*/
class UnionFindSets{
//parentOf[i]是i的父亲，比如parentOf[1] = 2就表示1的父亲是2
private int[] parentOf;
//构造方法
public UnionFindSets(int n){
parentOf = new int[n];
//一开始所有元素都在各自的集合中，因此i的父亲就是i本身
for(int i = 0; i < n; i++)
parentOf[i] = i;
}
//获取元素i所在集合的代表元素
private int getPresentOf(int i){
//如果i就是代表元素，则直接返回i
if(parentOf[i] == i)
return i;
//如果i的父亲不是i本身，则继续递归调用；注意这里使用了路径压缩：
//1. 假如1的父亲是2，2的父亲是3，3的父亲是3，那么在调用getPresentOf(1)后，会将1的父亲指定为3
//2. 路径压缩后代表元素的秩可能会减小，因此路径压缩可能会影响按秩合并的准确性
return parentOf[i] = getPresentOf(parentOf[i]);
}
//合并元素i所在集合与元素j所在集合，如果i和j在同一个集合内，则直接返回false
public boolean union(int i, int j){
int p1 = getPresentOf(i), p2 = getPresentOf(j);
if(p1 == p2)
return false;
//将p2指定为p1的父亲（也可以反过来，影响不大）
parentOf[p1] = p2;
return true;
}
//计算总共有多少个集合（也就是计算有多少个代表元素）
public int getGroupCount(){
int count = 0;
for(int i = 0; i < parentOf.length; i++){
if(parentOf[i] == i)
count++;
}
return count;
}
} 
查看21道真题和解析
