# [LeetCode] 261. Graph Valid Tree 图是不是树

2021年09月15日 阅读数：2

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.html

For example:java

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

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

Hint:app

1. Given `n = 5` and `edges = [[0, 1], [1, 2], [3, 4]]`, what should your return? Is this case a valid tree?
2. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

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`.post

Java: DFS

```public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}

for(int[] edge: edges){
}

boolean[] visited = new boolean[n];

if(!helper(0, -1, map, visited))
return false;

for(boolean b: visited){
if(!b)
return false;
}

return true;
}

public boolean helper(int curr, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
if(visited[curr])
return false;

visited[curr] = true;

for(int i: map.get(curr)){
if(i!=parent && !helper(i, curr, map, visited)){
return false;
}
}

return true;
}　```

Java: BFS

```public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}

for(int[] edge: edges){
}

boolean[] visited = new boolean[n];

queue.offer(0);
while(!queue.isEmpty()){
int top = queue.poll();
if(visited[top])
return false;

visited[top]=true;

for(int i: map.get(top)){
if(!visited[i])
queue.offer(i);
}
}

for(boolean b: visited){
if(!b)
return false;
}

return true;　```

Java：BFS

```public class Solution {
/**
* @param n an integer
* @param edges a list of undirected edges
* @return true if it's a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
if (n == 0) {
return false;
}

if (edges.length != n - 1) {
return false;
}

Map<Integer, Set<Integer>> graph = initializeGraph(n, edges);

// bfs
Set<Integer> hash = new HashSet<>();

queue.offer(0);
while (!queue.isEmpty()) {
int node = queue.poll();
for (Integer neighbor : graph.get(node)) {
if (hash.contains(neighbor)) {
continue;
}
queue.offer(neighbor);
}
}

return (hash.size() == n);
}

private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new HashSet<Integer>());
}

for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
}

return graph;
}
}
```

Java: Union Find

```public class Solution {
class UnionFind{
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
UnionFind(int n){
for(int i = 0 ; i < n; i++) {
father.put(i, i);
}
}
int compressed_find(int x){
int parent =  father.get(x);
while(parent!=father.get(parent)) {
parent = father.get(parent);
}
int temp = -1;
int fa = father.get(x);
while(fa!=father.get(fa)) {
temp = father.get(fa);
father.put(fa, parent) ;
fa = temp;
}
return parent;

}

void union(int x, int y){
int fa_x = compressed_find(x);
int fa_y = compressed_find(y);
if(fa_x != fa_y)
father.put(fa_x, fa_y);
}
}
/**
* @param n an integer
* @param edges a list of undirected edges
* @return true if it's a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
// tree should have n nodes with n-1 edges
if (n - 1 != edges.length) {
return false;
}

UnionFind uf = new UnionFind(n);

for (int i = 0; i < edges.length; i++) {
if (uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])) {
return false;
}
uf.union(edges[i][0], edges[i][1]);
}
return true;
}
}　　```

Python: DFS

```class Solution(object):
def validTree(self, n, edges):
lookup = collections.defaultdict(list)
for edge in edges:
lookup[edge[0]].append(edge[1])
lookup[edge[1]].append(edge[0])
visited = [False] * n

if not self.helper(0, -1, lookup, visited):
return False

for v in visited:
if not v:
return False

return True

def helper(self, curr, parent, lookup, visited):
print curr, visited
if visited[curr]:
return False
visited[curr] = True
for i in lookup[curr]:
if (i != parent and not self.helper(i, curr, lookup, visited)):
return False

return True

if __name__ == '__main__':
print Solution().validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])
print Solution().validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])　```

Python: BFS, Time: O(|V| + |E|), Space: O(|V| + |E|)

```class Solution(object):
# @param {integer} n
# @param {integer[][]} edges
# @return {boolean}
def validTree(self, n, edges):
if len(edges) != n - 1:  # Check number of edges.
return False

# init node's neighbors in dict
neighbors = collections.defaultdict(list)
for u, v in edges:
neighbors[u].append(v)
neighbors[v].append(u)

# BFS to check whether the graph is valid tree.
visited = {}
q = collections.deque([0])
while q:
curr = q.popleft()
visited[curr] = True
for node in neighbors[curr]:
if node not in visited:
visited[node] = True
q.append(node)

return len(visited) == n
```

Python: Union Find

```class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
root = [i for i in range(n)]
for i in edges:
root1 = self.find(root, i[0])
root2 = self.find(root, i[1])
if root1 == root2:
return False
else:
root[root1] = root2
return len(edges) == n - 1

def find(self, root, e):
if root[e] == e:
return e
else:
root[e] = self.find(root, root[e])
return root[e]　　```

C++: DFS

```class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> g(n, vector<int>());
vector<bool> v(n, false);
for (auto a : edges) {
g[a.first].push_back(a.second);
g[a.second].push_back(a.first);
}
if (!dfs(g, v, 0, -1)) return false;
for (auto a : v) {
if (!a) return false;
}
return true;
}
bool dfs(vector<vector<int>> &g, vector<bool> &v, int cur, int pre) {
if (v[cur]) return false;
v[cur] = true;
for (auto a : g[cur]) {
if (a != pre) {
if (!dfs(g, v, a, cur)) return false;
}
}
return true;
}
};
```

C++: BFS

```class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<unordered_set<int>> g(n, unordered_set<int>());
unordered_set<int> s{{0}};
queue<int> q{{0}};
for (auto a : edges) {
g[a.first].insert(a.second);
g[a.second].insert(a.first);
}
while (!q.empty()) {
int t = q.front(); q.pop();
for (auto a : g[t]) {
if (s.count(a)) return false;
s.insert(a);
q.push(a);
g[a].erase(t);
}
}
return s.size() == n;
}
};
```

C++: Union Find

```class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> roots(n, -1);
for (auto a : edges) {
int x = find(roots, a.first), y = find(roots, a.second);
if (x == y) return false;
roots[x] = y;
}
return edges.size() == n - 1;
}
int find(vector<int> &roots, int i) {
while (roots[i] != -1) i = roots[i];
return i;
}
};
```

[LeetCode] 200. Number of Islands 岛屿的数量

[LeetCode] 305. Number of Islands II 岛屿的数量之二

[LeetCode] 323. Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数