Graph Valid Tree
Total Accepted: 10169 Total Submissions: 31882 Difficulty: Medium
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.
BFS思路
- 首先想到了BFS的方法
- 用hashmap, Map> 这样O(m)就能得到neighbor点,m是edges数量
- 得到了neighbor点,就只需要BFS就可以了,注意不是valid的条件,就是两个点(不包括之前遍历的)指向了同一个点(有cycle),或者有的点没有neighbor,这样就不能构成tree
- 最终时间复杂度还是O(n + m)
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (n <= 0) {
return false;
}
if (n == 1) {
return true;
}
if (edges.length * 2 < n) {
return false;
}
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
int[] occur = new int[n];
for (int i = 0; i < edges.length; i++) {
int cur = edges[i][0];
int direction = edges[i][1];
occur[cur]++;
occur[direction]++;
if (!map.containsKey(cur)) {
List<Integer> list = new ArrayList<Integer>();
list.add(direction);
map.put(cur, list);
} else {
List<Integer> list = map.get(cur);
list.add(direction);
map.put(cur, list);
}
if (!map.containsKey(direction)) {
List<Integer> list = new ArrayList<Integer>();
list.add(cur);
map.put(direction, list);
} else {
List<Integer> list = map.get(direction);
list.add(cur);
map.put(direction, list);
}
}
for (int i = 0; i < n; i++) {
if (occur[i] == 0) {
return false;
}
}
int[] visited = new int[n];
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(0);
visited[0] = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
List<Integer> neighbor = map.get(cur);
for (int j = 0; j < neighbor.size(); j++) {
int next = neighbor.get(j);
if (!map.containsKey(next)) {
continue;
}
if (visited[next] == 1) {
return false;
}
queue.offer(next);
visited[next] = 1;
}
map.remove(cur);
}
}
return map.size() == 0;
}
}
Union Find思路
- Compress Union Find
- 找节点
- 一个n个节点树有且必须有n-1条边
- 如果n个节点树有且必须有n-1条边也是无效的,只有一种原因,就是有cycle存在无效边
- 如果Union find的时候,一个edges对里边,两个点一定相连,如果这两个相连的点parent一样,那么一定存在环了
public class Solution {
public boolean validTree(int n, int[][] edges) {
if(n <= 1) {
return true;
}
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < edges.length; i++) {
int x = find(parent, edges[i][0]);
int y = find(parent, edges[i][1]);
if (x == y) {
return false;
}
union(parent, x, y);
}
return edges.length == n - 1;
}
public int find(int[] parent, int i) {
int father = parent[i];
while (father != parent[father]) {
father = parent[father];
}
int index = i;
while (index != parent[index]) {
int temp = parent[index];
parent[index] = father;
index = temp;
}
return father;
}
public void union(int[] parent, int x, int y) {
int root_x = find(parent, x);
int root_y = find(parent, y);
if (root_x != root_y) {
parent[root_y] = root_x;
}
}
}