add DFS solution for 207

fishercoder1534 · fishercoder1534 · commit bbc057d5aa4f · 2020-05-26T08:34:53.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_207.java b/src/main/java/com/fishercoder/solutions/_207.java
@@ -1,8 +1,12 @@
 package com.fishercoder.solutions;
 
+import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
 import java.util.Queue;
 import java.util.Set;
 
@@ -85,4 +89,46 @@ public boolean canFinish(int numCourses, int[][] prerequisites) {
             return true;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * DFS, the fastest method in all, with the help of a cache and also converted edges into adjacency list,
+         * although theoretically, all these three methods' time complexity is: O(V+E)
+         */
+        public boolean canFinish(int numCourses, int[][] prerequisites) {
+            List<List<Integer>> courseList = new ArrayList<>();
+            for (int i = 0; i < numCourses; i++) {
+                courseList.add(new ArrayList<>());
+            }
+            for (int[] pre : prerequisites) {
+                courseList.get(pre[1]).add(pre[0]);
+            }
+            int[] visited = new int[numCourses];
+            //visit each course using DFS
+            for (int i = 0; i < numCourses; i++) {
+                if (!dfs(i, courseList, visited)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private boolean dfs(int course, List<List<Integer>> courseList, int[] visited) {
+            visited[course] = 1;//mark as temporarily visited
+            List<Integer> coursesCanBeTaken = courseList.get(course);
+            for (int i = 0; i < coursesCanBeTaken.size(); i++) {
+                int courseToTake = coursesCanBeTaken.get(i);
+                if (visited[courseToTake] == 1) {
+                    return false;
+                }
+                if (visited[courseToTake] == 0) {
+                    if (!dfs(courseToTake, courseList, visited)) {
+                        return false;
+                    }
+                }
+            }
+            visited[course] = 2;//mark it as completely done.
+            return true;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_207Test.java b/src/test/java/com/fishercoder/_207Test.java
@@ -9,13 +9,15 @@
 public class _207Test {
     private static _207.Solution1 solution1;
     private static _207.Solution2 solution2;
+    private static _207.Solution3 solution3;
     private static int[][] prerequisites;
     private static int numCourses;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _207.Solution1();
         solution2 = new _207.Solution2();
+        solution3 = new _207.Solution3();
     }
 
     @Test
@@ -24,6 +26,7 @@ public void test1() {
         prerequisites = new int[][]{{0, 1}};
         assertEquals(true, solution1.canFinish(numCourses, prerequisites));
         assertEquals(true, solution2.canFinish(numCourses, prerequisites));
+        assertEquals(true, solution3.canFinish(numCourses, prerequisites));
     }
 
     @Test
@@ -43,6 +46,7 @@ public void test2() {
         };
         assertEquals(true, solution1.canFinish(numCourses, prerequisites));
         assertEquals(true, solution2.canFinish(numCourses, prerequisites));
+        assertEquals(true, solution3.canFinish(numCourses, prerequisites));
     }
 
     @Test
@@ -62,5 +66,6 @@ public void test3() {
         };
         assertEquals(true, solution1.canFinish(numCourses, prerequisites));
         assertEquals(true, solution2.canFinish(numCourses, prerequisites));
+        assertEquals(true, solution3.canFinish(numCourses, prerequisites));
     }
 }
