Create 1059.All-Paths-from-Source-Lead-to-Destination.cpp

wisdompeak · web-flow · commit 2f72153999d8 · 2021-01-27T20:52:53.000-08:00
diff --git a/Graph/1059.All-Paths-from-Source-Lead-to-Destination/1059.All-Paths-from-Source-Lead-to-Destination.cpp b/Graph/1059.All-Paths-from-Source-Lead-to-Destination/1059.All-Paths-from-Source-Lead-to-Destination.cpp
@@ -0,0 +1,38 @@
+class Solution {
+    int visited[10001];
+    vector<vector<int>>nextNodes;
+public:
+    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) 
+    {
+        nextNodes.resize(n+1);
+        for (auto edge: edges)
+            nextNodes[edge[0]].push_back(edge[1]);
+        
+        return dfs(source, destination);        
+    }
+    
+    bool dfs(int cur, int dest)
+    {
+        visited[cur] = 2;
+        if (nextNodes[cur].size() == 0)
+        {
+            if (cur!=dest)
+                return false;
+            else
+            {
+                visited[cur] = 1;
+                return true;
+            }                
+        }
+        
+        for (auto next: nextNodes[cur])
+        {
+            if (visited[next]==1) continue;
+            if (visited[next]==2) return false;
+            if (dfs(next, dest)==false)
+                return false;
+        }
+        visited[cur] = 1;
+        return true;
+    }
+};
