261. Graph Valid Tree

题目：

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:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? Show More Hint

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.

链接： http://leetcode.com/problems/graph-valid-tree/

5/13/2017

算法班，抄答案

8ms, 39%

被hashCode跑偏了，没有想起来怎么做这道题。

最后用顶点做hashset比用边要好。因为用边不容易检测到环。

http://www.jiuzhang.com/solutions/graph-valid-tree/

 1 public class Solution {
 2 
 3     public boolean validTree(int n, int[][] edges) {
 4         // make sure E == V - 1
 5         if (edges == null || edges.length != n - 1) {
 6             return false;
 7         }
 8         Map<Integer, Set<Integer>> graph = initializeGraph(n, edges);
 9         Queue<Integer> queue = new LinkedList<Integer>();
10         Set<Integer> set = new HashSet<Integer>();
11         queue.offer(0);
12         set.add(0);
13         
14         while (!queue.isEmpty()) {
15             Integer v = queue.poll();
16             for (Integer neighbor: graph.get(v)) {
17                 if (!set.contains(neighbor)) {
18                     queue.offer(neighbor);
19                     set.add(neighbor);
20                 }
21             }
22         }
23         return set.size() == n;
24     }
25     private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) {
26         Map<Integer, Set<Integer>> map = new HashMap<>();
27         
28         for (int i = 0; i < n; i++) {
29             map.put(i, new HashSet<Integer>());
30         }
31         for (int i = 0; i < edges.length; i++) {
32             int e = edges[i][0];
33             int o = edges[i][1];
34             map.get(e).add(o);
35             map.get(o).add(e);
36         }
37         return map;
38     }
39 }

顺便实现了一次hashCode

 1     class Edge {
 2         final int either, other;
 3         Edge(int[] edge) {
 4             if (edge[0] < edge[1]) {
 5                 this.either = edge[0];
 6                 this.other = edge[1];                
 7             } else {
 8                 this.other = edge[0];
 9                 this.either = edge[1];
10             }
11         }
12         @Override
13         public boolean equals(Object obj) {
14             if (obj == null) return false;
15             if (!(obj instanceof Edge)) return false;
16             Edge o = (Edge) obj;
17             if (o.either == this.either && o.other == this.other) {
18                 // because we already ordered the two V, no need to check other direction
19                 return true;
20             }
21             return false;
22         }
23         @Override
24         public int hashCode() {
25             int hash = 7;
26             hash = 71 * hash + this.either;
27             hash = 71 * hash + this.other;
28             return hash;        
29         }
30     }

还有union-find的方法。

1ms, 73%

 1 public class Solution {
 2     class WeightedUnionFind {
 3         int[] parent;
 4         int[] size;
 5         
 6         WeightedUnionFind(int n) {
 7             parent = new int[n];
 8             size = new int[n];
 9             for (int i = 0; i < n; i++) {
10                 parent[i] = i;
11                 size[i] = 1;
12             }
13         }
14         int find(int p) {
15             while (parent[p] != p) {
16                 parent[p] = parent[parent[p]]; //1-pass path compression, every other node in the path points to its grandfather
17                 p = parent[p];
18             }
19             return p;
20         }
21         void union(int p, int q) {
22             int rootP = find(p);
23             int rootQ = find(q);
24             // check if already connected or not
25             if (rootP == rootQ) {
26                 return;
27             }
28             if (size[rootP] < size[rootQ]) {
29                 parent[rootP] = rootQ;
30                 size[rootQ] += size[rootQ];
31             } else {
32                 parent[rootQ] = rootP;
33                 size[rootP] += size[rootQ];
34             }
35         }
36         boolean connected(int p, int q) {
37             return find(p) == find(q);
38         }
39     }
40     public boolean validTree(int n, int[][] edges) {
41         if (edges == null || edges.length != n - 1) return false;
42         WeightedUnionFind uf = new WeightedUnionFind(n);
43         for (int i = 0; i < edges.length; i++) {
44             int p = edges[i][0];
45             int q = edges[i][1];
46             if (uf.connected(p, q)) return false;
47             uf.union(edges[i][0], edges[i][1]);
48         }
49         return true;
50     }
51 }