[Function add]

Seanforfun · Seanforfun · commit c465d51f43f3 · 2019-03-25T18:23:09.000-04:00
1. Add leetcode solutions with tag graph.
diff --git a/leetcode/207. Course Schedule.md b/leetcode/207. Course Schedule.md
@@ -141,5 +141,40 @@ class Solution {
 }
 ```
 
+### Third Time
+* Method 1: Topological sort + bfs
+	```Java
+	class Solution {
+		public boolean canFinish(int numCourses, int[][] prerequisites) {
+			Map<Integer, List<Integer>> map = new HashMap<>();
+			int[] indegree = new int[numCourses];
+			Set<Integer> remain = new HashSet<>();
+			for(int i = 0; i < numCourses; i++) remain.add(i);
+			for(int[] req : prerequisites){
+				indegree[req[1]]++;
+				List<Integer> next = map.containsKey(req[0]) ? map.get(req[0]): new ArrayList<Integer>();
+				next.add(req[1]);
+				map.put(req[0], next);
+			}
+			Queue<Integer> queue = new LinkedList<>();
+			for(int i = 0; i < numCourses; i++){
+				if(indegree[i] == 0)
+					queue.offer(i);
+			}
+			while(!queue.isEmpty()){
+				int course = queue.poll();
+				remain.remove(course);
+				List<Integer> courses = map.get(course);
+				if(courses == null) continue;
+				for(Integer c : courses){
+					if(--indegree[c] == 0)
+						queue.offer(c);
+				}
+			}
+			return remain.isEmpty();
+		}
+	}
+	```
+
 ### Reference
 1. [【图论】有向无环图的拓扑排序](https://www.cnblogs.com/en-heng/p/5085690.html)
diff --git a/leetcode/210. Course Schedule II.md b/leetcode/210. Course Schedule II.md
@@ -151,4 +151,48 @@ class Solution {
         }
     }
 }
-```
+```
+
+### Third Time
+* Method 1: Topological sort + bfs
+	```Java
+	class Solution {
+		public int[] findOrder(int numCourses, int[][] prerequisites) {
+			int[] order = new int[numCourses];
+			int[] indegree = new int[numCourses];
+			int index = 0;
+			Map<Integer, List<Integer>> map = new HashMap<>();
+			Set<Integer> remain = new HashSet<>();
+			for(int i = 0; i < numCourses; i++) remain.add(i);
+			for(int[] req : prerequisites){
+				indegree[req[0]]++;
+				List<Integer> nexts = map.containsKey(req[1]) ? map.get(req[1]): new ArrayList<>();
+				nexts.add(req[0]);
+				map.put(req[1], nexts);
+			}
+			Queue<Integer> queue = new LinkedList<>();
+			for(int i = 0; i < numCourses; i++){
+				if(indegree[i] == 0){
+					queue.offer(i);
+				}
+			}
+			while(!queue.isEmpty()){
+				int cur = queue.poll();
+				remain.remove(cur);
+				List<Integer> courses = map.get(cur);
+				order[index++] = cur;
+				if(courses == null){
+					remain.remove(cur);
+				}else{
+					for(Integer course : courses){
+						indegree[course]--;
+						if(indegree[course] == 0){
+							queue.offer(course);
+						}
+					}
+				}
+			}
+			return remain.isEmpty() ? order: new int[0];
+		}
+	}
+	```
diff --git a/leetcode/802. Find Eventual Safe States.md b/leetcode/802. Find Eventual Safe States.md
@@ -0,0 +1,73 @@
+## 802. Find Eventual Safe States
+
+### Question:
+In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.
+
+Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.
+
+Which nodes are eventually safe?  Return them as an array in sorted order.
+
+The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph.  The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.
+
+```
+Example:
+Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
+Output: [2,4,5,6]
+Here is a diagram of the above graph.
+```
+
+Illustration of graph
+![Imgur](https://i.imgur.com/1oOwEFl.png)
+
+Note:
+* graph will have length at most 10000.
+* The number of edges in the graph will not exceed 32000.
+* Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].
+
+### Solution:
+* Method 1: dfs + graph
+   * This question is about to find the nodes who is not in a cycle, which means itself and its children are not in a cycle.
+   * We take 4 states to record a node's status
+        * {UNKNOW, VISIT, SAFE, UNSAFE}
+        * UNKNOWN: current node is not visited. Initialized status.
+        * VISIT: current node is in the process of dfs. UNKNOW -> VISIT
+        * SAFE: current node is safe.       All childs are SAFE -> current is SAFE
+        * UNSAFE: current node is unsafe.   VISIT -> UNSAFE
+    ```Java
+    class Solution {
+        private static final int UNKNOWN = 0;
+        private static final int VISIT = 1;
+        private static final int SAFE = 2;
+        private static final int UNSAFE = 3;
+        private int[] state;
+        private int len;
+        public List<Integer> eventualSafeNodes(int[][] graph) {
+            List<Integer> result = new ArrayList<>();
+            if(graph == null || graph.length == 0) return result;
+            len = graph.length;
+            state = new int[len];
+            for(int i = 0; i < len; i++){
+                if(dfs(graph, i) == SAFE)
+                    result.add(i);
+            }
+            return result;
+        }
+        private int dfs(int[][] graph, int cur){
+            if(state[cur] == VISIT){
+                return state[cur] = UNSAFE;
+            }else if(state[cur] != UNKNOWN){
+                return state[cur];
+            }
+            state[cur] = VISIT;
+            for(int i = 0; i < graph[cur].length; i++){
+                if(dfs(graph, graph[cur][i]) == UNSAFE){
+                    return state[cur] = UNSAFE;
+                }
+            }
+            return state[cur] = SAFE;
+        }
+    }
+    ```
+   
+### Reference
+1. [花花酱 LeetCode 802. Find Eventual Safe States](http://zxi.mytechroad.com/blog/graph/leetcode-802-find-eventual-safe-states/)
