261. Graph Valid Tree

时间:2021-06-18 21:49:18

题目:

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

  1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? Show More Hint

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

链接: http://leetcode.com/problems/graph-valid-tree/

题解:

验证输入数组是否能组成一个树。看了一些资料,这属于并查集的问题。首先我们明确一下满足要求的解的条件:

  1. 题目给定了n个node,则假如能组成一棵树,则这棵树的edge数目为n - 1,所以我们一开始要判断edges.length == n - 1
  2. 不可以有环路,即这个无向图必须是acyclic的, 所有的edges最后也只能组成一个connected components

在判断完edges.length == n - 1后, 我们可以想到使用Union-Find中的Quick-Find。先构造一个长为节点数n的数组id,初始化数组每个元素与他们的index相等。接下来遍历无向图的edges矩阵,假如edges[i][0]和edges[i][1]已经联通,则这个图存在环,我们返回false,否则我们把这两个元素联通起来 - 遍历id数组,将其中所有值为pid的元素值更新为qid。数组遍历结束之后返回true。  Quadratic time还是非常巨大,所以我们还可以继续对这个方法进行优化,接下来的就是Weighted Quick Union + Path Compression了, 留给二刷,继续前进。 收获是接触到了并查集的概念,很高兴。

Time Complexity - O(n2), Space Complexity - O(n)

public class Solution {
public boolean validTree(int n, int[][] edges) { // dynamic connectivity
if(n < 0 || edges == null || edges.length != n - 1)
return false;
int[] id = new int[n];
for(int i = 0; i < id.length; i++) {
id[i] = i;
} for(int i = 0; i < edges.length; i++) {
if(!connected(id, edges[i][0], edges[i][1])) {
union(id, edges[i][0], edges[i][1]);
} else {
return false;
}
}
return true;
} private boolean connected(int[] id, int p, int q) {
return id[p] == id[q];
} private void union(int[] id, int p, int q) {
int pid = id[p];
int qid = id[q];
for(int i = 0; i < id.length; i++) {
if(id[i] == pid) {
id[i] = qid;
}
}
}
}

二刷:

首先检测边界条件, 是否edges.length == n - 1。 其次转化为无向图检测环路,我们可以使用Union-Find来做。

下面是Weighted Quick Union + Path Compression,一如Sedgewick大神教授的。

Java:

public class Solution {
private int[] id;
private int[] sz;
public boolean validTree(int n, int[][] edges) {
if (n < 0 || edges == null || edges.length != n - 1) {
return false;
}
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
sz[i] = 1;
}
for (int i = 0; i < edges.length; i++) {
if (!isConnected(edges[i][0], edges[i][1])) {
union(edges[i][0], edges[i][1]);
} else {
return false;
}
}
return true;
} private int getRoot(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
} private void union(int i, int j) {
int rootI = getRoot(i);
int rootJ = getRoot(j);
if (rootI == rootJ) {
return;
}
if (sz[rootI] < sz[rootJ]) {
id[rootI] = rootJ;
sz[rootJ] += sz[rootI];
} else {
id[rootJ] = rootI;
sz[rootI] += sz[rootJ];
}
} private boolean isConnected(int i, int j) {
return getRoot(i) == getRoot(j);
}
}

Reference:

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://www.youtube.com/watch?v=4SZTsQO9d6k&index=3&list=PLe-ggMe31CTexoNYnMhbHaWhQ0dvcy43t

https://en.wikipedia.org/wiki/Tree_(data_structure)

http://segmentfault.com/a/1190000003791051

http://blog.csdn.net/dm_vincent/article/details/7655764

http://blog.csdn.net/pointbreak1/article/details/48796691

http://nb4799.neu.edu/wordpress/?p=1143

http://algorithmsandme.in/2014/06/graphs-detecting-cycle-in-undirected-graph/

http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf

https://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/UnionFind.pdf

https://leetcode.com/discuss/52610/8-10-lines-union-find-dfs-and-bfs

https://leetcode.com/discuss/52563/ac-java-union-find-solution

https://leetcode.com/discuss/58600/a-java-solution-with-dfs

https://leetcode.com/discuss/72645/compressed-weighted-quick-union-solution-in-java-2ms