261 Graph Valid Tree

Search…
261. Graph Valid Tree​
1. Question
Givennnodes labeled from0ton - 1and 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:
Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.
Note: you can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.
2. Implementation
(1) BFS
1
class Solution {
2
    public boolean validTree(int n, int[][] edges) {
3
        List<Set<Integer>> adjList = new ArrayList<>();
4
​
5
        for (int i = 0; i < n; i++) {
6
           adjList.add(new HashSet<>());
7
        }
8
​
9
        for (int[] edge : edges) {
10
           adjList.get(edge[0]).add(edge[1]);
11
           adjList.get(edge[1]).add(edge[0]);
12
        }
13
​
14
        boolean[] visited = new boolean[n];
15
        Queue<Integer> queue = new LinkedList<>();
16
        queue.add(0);
17
​
18
        while (!queue.isEmpty()) {
19
            int curNode = queue.remove();
20
​
21
            // found loop
22
            if (visited[curNode]) {
23
                return false;
24
            }
25
​
26
            visited[curNode] = true;
27
​
28
            for (int nextNode : adjList.get(curNode)) {
29
                queue.add(nextNode);
30
                adjList.get(nextNode).remove(curNode);
31
            }
32
        }
33
​
34
        for (boolean e : visited) {
35
            if (!e) {
36
                return false;
37
            }
38
        }
39
        return true;
40
    }
41
}
Copied!
(2) DFS
1
class Solution {
2
    public boolean validTree(int n, int[][] edges) {
3
        List<Set<Integer>> adjList = new ArrayList<>();
4
​
5
        for (int i = 0; i < n; i++) {
6
            adjList.add(new HashSet<>());
7
        }
8
​
9
        for (int[] edge : edges) {
10
            adjList.get(edge[0]).add(edge[1]);
11
            adjList.get(edge[1]).add(edge[0]);
12
        }
13
​
14
        boolean[] visited = new boolean[n];
15
​
16
        // Check if graph has cycle
17
        if (hasCycle(0, visited, adjList, -1)) {
18
            return false;
19
        }
20
​
21
        // Check if graph is connected
22
        for (int i = 0; i < n; i++) {
23
            if (!visited[i]) {
24
                return false;
25
            }
26
        }
27
        return true;
28
    }
29
​
30
    public boolean hasCycle(int node, boolean[] visited, List<Set<Integer>> adjList, int parent) {
31
        visited[node] = true;
32
​
33
        for (int nextNode : adjList.get(node)) {
34
            // (1) If nextNode is visited but it is not the parent of the curNode, then there is cycle
35
            // (2) If nextNode is not visited but we still find the cycle later on, return true;
36
            if ((visited[nextNode] && parent != nextNode) || (!visited[nextNode] && hasCycle(nextNode, visited, adjList, node))) {
37
                return true;
38
            }
39
        }
40
        return false;
41
    }
42
}
Copied!
(3) Union Find
1
class Solution {
2
    public boolean validTree(int n, int[][] edges) {
3
        UnionFind uf = new UnionFind(n);
4
​
5
        for (int[] edge : edges) {
6
            // Find Loop
7
            if (!uf.union(edge[0], edge[1])) {
8
                return false;
9
            }
10
        }
11
        // Make sure the graph is connected
12
        return uf.count == 1;
13
    }
14
​
15
    class UnionFind {
16
        int[] sets;
17
        int[] size;
18
        int count;
19
​
20
        public UnionFind(int n) {
21
            sets = new int[n];
22
            size = new int[n];
23
            count = n;
24
​
25
            for (int i = 0; i < n; i++) {
26
                sets[i] = i;
27
                size[i] = 1;
28
            }
29
        }
30
​
31
        public int find(int node) {
32
            while (node != sets[node]) {
33
                node = sets[node];
34
            }
35
            return node;
36
        }
37
​
38
        public boolean union(int i, int j) {
39
            int node1 = find(i);
40
            int node2 = find(j);
41
​
42
            if (node1 == node2) {
43
                return false;
44
            }
45
​
46
            if (size[node1] < size[node2]) {
47
                sets[node1] = node2;
48
                size[node2] += size[node1];
49
            }
50
            else {
51
                sets[node2] = node1;
52
                size[node1] += size[node2];
53
            }
54
            --count;
55
            return true;
56
        }
57
    }
58
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(n), 空间复杂度O(n)
DFS: 时间复杂度O(n), 空间复杂度O(n)
Union Find: 时间复杂度O(n), 空间复杂度O(n)
200 Number of Islands
305 Number of Islands II
Last modified 2yr ago
Copy link
Contents
261. Graph Valid Tree
1. Question
2. Implementation
3. Time & Space Complexity
261. Graph Valid Tree​

1. Question

2. Implementation

3. Time & Space Complexity

261. Graph Valid Tree
