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

Union Find

树是无环的联通图，所以一个无向图做为树需满足如下条件

  1. 边的数量 = n - 1
  2. 用union find连接每一个点，不能出现两个点，已经连接的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean validTree(int n, int[][] edges) {
    if (n <= 0 || edges == null)
        return false;
    if (edges.length != n - 1)
        return false;
    int[] fathers = new int[n];
    for (int i = 0; i < n; i++) {
        fathers[i] = i;
    }
    for (int[] edge : edges) {
        int fax = find(fathers, edge[0]);
        int fay = find(fathers, edge[1]);
        if (fax == fay)
            return false;
        fathers[fax] = fay;
    }
    return true;
}
private int find(int[] fathers, int x) {
    int fa = fathers[x];
    while (fa != fathers[fa]) {
        fa = fathers[fa];
    }
    return fa;
}

DFS

DFS和BFS都不是自己写的，有机会自己再写一下吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private boolean validDFS(int n, int[][] edges) {
    // build the graph using adjacent list
    List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
    for (int i = 0; i < n; i++)
        graph.add(new HashSet<Integer>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }
    // no cycle
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<Integer>();
    stack.push(0);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node])
            return false;
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            stack.push(neighbor);
            graph.get(neighbor).remove(node);
        }
    }
    // fully connected
    for (boolean result : visited) {
        if (!result)
            return false;
    }
    return true;
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private boolean valid(int n, int[][] edges) {
    // build the graph using adjacent list
    List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
    for (int i = 0; i < n; i++)
        graph.add(new HashSet<Integer>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }
    // no cycle
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<Integer>();
    queue.add(0);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (visited[node])
            return false;
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            queue.offer(neighbor);
            graph.get(neighbor).remove((Integer) node);
        }
    }
    // fully connected
    for (boolean result : visited) {
        if (!result)
            return false;
    }
    return true;
}

Ref: https://discuss.leetcode.com/topic/22486/ac-java-solutions-union-find-bfs-dfs