• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true


Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false


Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• $0 <= a_i, b_i < n$
• $a_i != b_i$
• There are no self-loops or repeated edges.

## Code

684. Redundant Connection

### Union Find

class Solution {
public class UnionFind {
int[] parents;
int[] ranks;

public UnionFind(int n) {
parents = new int[n];
ranks = new int[n];

for (int i = 0; i < n; i++) {
parents[i] = i;
ranks[i] = 1;
}
}

public boolean union(int x, int y) {
int xParent = find(x);
int yParent = find(y);

if (xParent == yParent) return false;

if (ranks[xParent] > ranks[yParent]) {
parents[yParent] = xParent;
} else if (ranks[xParent] < ranks[yParent]) {
parents[xParent] = yParent;
} else {
parents[yParent] = xParent;
ranks[xParent]++;
}

return true;
}

public int find(int node) {
if(node == parents[node]) return node;

return find(parents[node]);
}
}

UnionFind node;
public boolean validTree(int n, int[][] edges) {
// 注意孤立点
// [0, 1], [2, 3] n = 4
// 这种情况也不是树
if(edges.length + 1 < n) return false;
node = new UnionFind(n);

for(int[] edge : edges){
if(!node.union(edge[0], edge[1])){
return false;
}
}

return true;
}
}

class UnionFind:
def __init__(self, n: int):
self.parents = [i for i in range(n)]
self.ranks = [1] * n

def union(self, u: int, v: int) -> bool:
pu = self.find(u)
pv = self.find(v)

if pu == pv:
return False

if self.ranks[pu] > self.ranks[pv]:
self.parents[pv] = pu
elif self.ranks[pu] < self.ranks[pv]:
self.parents[pu] = pv
else:
self.parents[pv] = pu
self.ranks[pu] += 1

return True

def find(self, u: int) -> int:
if self.parents[u] == u:
return u

return self.find(self.parents[u])

class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False

node = UnionFind(n)

for edge in edges:
if not node.union(edge[0], edge[1]):
return False

return True

// find 也可以写成下面的形式
public int find(int node) {
while (node != parents[node]) {
int parentNode = parents[parents[node]];
node = parentNode;
}

return node;
}


Time Complexity: O(N⋅α(N)) Space Complexity: O(N)

### DFS

class Solution {
public boolean validTree(int n, int[][] edges) {
if(n == 1) {
return true;
}

HashMap<Integer, List<Integer>> graph = new HashMap<>();

for(int[] edge : edges) {
if(!graph.containsKey(edge[0])) {
graph.put(edge[0], new ArrayList<>());
}

if(!graph.containsKey(edge[1])) {
graph.put(edge[1], new ArrayList<>());
}

}

HashSet<Integer> visited = new HashSet<>();

boolean res = helper(graph, visited, 0, -1);

if(!res) {
return false;
}

return visited.size() == n;
}

private boolean helper(HashMap<Integer, List<Integer>> graph, HashSet<Integer> visited, int curr, int parent) {
if(!graph.containsKey(curr)) {
return false;
}
List<Integer> subs = graph.get(curr);

for(int sub : subs) {
if(parent == sub){
continue;
}

if(visited.contains(sub)){
return false;
}

boolean res = helper(graph, visited, sub, curr);
if(!res){
return false;
}
}

return true;
}
}

class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# 1. 不会构成连通图
# 2. 没有孤立的点
graph = defaultdict(list)

for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])

visited = set()

res = self.helper(graph, visited, 0, -1)

if not res:
return False

return True if len(visited) == n else False

def helper(self, graph: List[List[int]], visited: Set[int], node: int, parent: int):
subs = graph[node]

for sub in subs:
if sub == parent:
continue

if sub in visited:
return False