fd

dingjikerbo · dingjikerbo · commit b8283aca4656 · 2017-12-07T21:25:05.000+08:00
diff --git a/solution/src/main/java/com/inuker/solution/GraphValidTree.java b/solution/src/main/java/com/inuker/solution/GraphValidTree.java
@@ -2,6 +2,11 @@
 
 /**
  * Created by dingjikerbo on 17/1/2.
+ * <p>
+ * 判断无向图是否带环，可采用UF, DFS, BFS。
+ * UF实现简单，性能很好
+ * <p>
+ * 题目中已声明不会有重复的边，类似[0,1]和[1,0]认为是重复的，也不会同时存在
  */
 /**
  * 判断无向图是否带环，可采用UF, DFS, BFS。
@@ -12,7 +17,11 @@
  */
 
 import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.List;
+import java.util.Queue;
+import java.util.Set;
 
 /**
  * 这题就是给了一堆边，看这些边构成的无向图会不会有环，另外这些边是不是都连在一起的
@@ -59,7 +68,7 @@ public boolean validTree(int n, int[][] edges) {
     }
 
     int find(int nums[], int i) {
-        for (; nums[i] != i; i = nums[i]);
+        for (; nums[i] != i; i = nums[i]) ;
         return i;
     }
 
@@ -77,22 +86,11 @@ public boolean validTree2(int n, int[][] edges) {
             graph[edges[i][0]].add(edges[i][1]);
             graph[edges[i][1]].add(edges[i][0]);
         }
-        boolean[] visited = new boolean[n];
-
-        /**
-         * 这里从任意一点开始DFS都可以
-         */
+        Set<Integer> visited = new HashSet<>();
         if (!dfs(graph, visited, 0, -1)) {
             return false;
         }
-
-        for (int i = 0; i < n; i++) {
-            if (!visited[i]) {
-                return false;
-            }
-        }
-
-        return true;
+        return visited.size() == n;
     }
 
     /**
@@ -101,22 +99,51 @@ public boolean validTree2(int n, int[][] edges) {
      * @parent 为了避免逆向遍历，因为parent肯定是访问过的，所以为了避免看作重复访问，这里排除了一下
      * @return 是否无环
      */
-    private boolean dfs(List<Integer>[] graph, boolean[] visited, int start, int parent) {
-        visited[start] = true;
-
-        for (int i = 0; i < graph[start].size(); i++) {
-            int to = graph[start].get(i);
-            if (to == parent) {
-                continue;
-            }
-            if (visited[to]) {
-                return false;
-            }
-            if (!dfs(graph, visited, to, start)) {
+    private boolean dfs(List<Integer>[] graph, Set<Integer> visited, int start, int parent) {
+        if (!visited.add(start)) {
+            return false;
+        }
+        for (Integer to : graph[start]) {
+            if (to != parent && !dfs(graph, visited, to, start)) {
                 return false;
             }
         }
-
         return true;
     }
+
+    /**
+     * BFS
+     */
+    public boolean validTree3(int n, int[][] edges) {
+        List<Integer>[] graph = new ArrayList[n];
+        for (int i = 0; i < n; i++) {
+            graph[i] = new ArrayList<>();
+        }
+        for (int i = 0; i < edges.length; i++) {
+            graph[edges[i][0]].add(edges[i][1]);
+            graph[edges[i][1]].add(edges[i][0]);
+        }
+        Set<Integer> visited = new HashSet<>();
+        Queue<Integer> queue = new LinkedList<>();
+
+        queue.offer(0);
+        visited.add(0);
+
+        while (!queue.isEmpty()) {
+            int k = queue.poll();
+
+            for (Integer near : graph[k]) {
+                if (!visited.add(near)) {
+                    return false;
+                }
+                queue.offer(near);
+                /**
+                 * 这个remove别掉了，且必须是Integer.valueOf，
+                 * 否则被当成index了
+                 */
+                graph[near].remove(Integer.valueOf(k));
+            }
+        }
+        return visited.size() == n;
+    }
 }
diff --git a/test/src/main/java/com/inuker/test/main.java b/test/src/main/java/com/inuker/test/main.java
@@ -6,6 +6,7 @@
 import com.leetcode.library.UndirectedGraphNode;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
