Leetcode210。爲什麼我的代碼在特定情況下是錯誤的？

Question

這是問題（https://leetcode.com/problems/course-schedule-ii/description/）。 而我的解決方案來自「算法導論」。 使用DFS算法。用白色，灰色和黑色對節點着色。

1. 將所有節點標記爲白色。
2. 當發現一個節點時，標記爲灰色。
3. 當一個節點完成時，標記爲黑色。
4. 當邊緣向後時，意味着有一個灰色的相鄰節點。它有一個圓圈，它應該是null。

但我通過大部分情況。但其中一些不是。 任何人都可以幫我嗎？

的代碼：

class Solution { 
public: 
    enum {WHITE, GRAY, BLACK}; 

    vector<vector<int>> graph; 
    vector<int> colors; 
    list<int> topo; 

    void add_edge(vector<vector<int>>& graph, pair<int, int>& p) { 
     graph[p.second].push_back(p.first); 
    } 
    bool visit(vector<vector<int>>& graph, int i) { 
     if (colors[i] == WHITE) { 
      colors[i] = GRAY; 
      bool ret = true; 

      for (int j = 0; j < graph[i].size(); j++) { 
       if (colors[graph[i][j]] == WHITE) 
        ret = ret && visit(graph, graph[i][j]); 
       else if (colors[graph[i][j]] == GRAY) 
        ret = false; 
       else 
        ret = false; 

      } 

      colors[i] = BLACK; 
      topo.push_front(i); 
      return ret; 
     } 

     return true; 
    } 

    bool dfs(vector<vector<int>>& graph) { 
     for (int i = 0; i < graph.size(); i++) 
      if (!visit(graph, i)) 
       return false; 
     return true; 
    } 



public: 
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) { 
     graph.resize(numCourses, {}); 
     colors.resize(numCourses, WHITE); 

     for (auto& pre: prerequisites) 
      add_edge(graph, pre); 

     if (!dfs(graph)) 
      return {}; 

     vector<int> ret (topo.begin(),topo.end()); 
     return ret; 
    } 
}; 

Answer 1

在

 for (int j = 0; j < graph[i].size(); j++) { 
      if (colors[graph[i][j]] == WHITE) 
       ret = ret && visit(graph, graph[i][j]); 
      else if (colors[graph[i][j]] == GRAY) 
       ret = false; 
      else 
       ret = false; 
     } 

最後別的是，當節點是黑色的，這意味着它已經處理並推入結果。所以它不會使圖表無效。只要刪除最後一個，它會起作用。像這樣：

 for (int j = 0; j < graph[i].size(); j++) { 
      if (colors[graph[i][j]] == WHITE) 
       ret = ret && visit(graph, graph[i][j]); 
      else if (colors[graph[i][j]] == GRAY) 
       ret = false; 
      /* else 
       ret = false; */ 
     }