?LeetCode刷題實(shí)戰(zhàn)210：課程表 II

示例 1:

輸入: 2, [[1,0]] 
輸出: [0,1]
解釋: 總共有 2 門課程。要學(xué)習(xí)課程 1，你需要先完成課程 0。因此，正確的課程順序?yàn)?[0,1] 。

示例 2:

輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后。
  因此，一個(gè)正確的課程順序是 [0,1,2,3] 。另一個(gè)正確的排序是 [0,2,1,3] 。

說明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請(qǐng)參見圖的表示法。
你可以假定輸入的先決條件中沒有重復(fù)的邊。

提示:

這個(gè)問題相當(dāng)于查找一個(gè)循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓?fù)渑判?，因此不可能選取所有課程進(jìn)行學(xué)習(xí)。
通過 DFS 進(jìn)行拓?fù)渑判?- 一個(gè)關(guān)于Coursera的精彩視頻教程（21分鐘），介紹拓?fù)渑判虻幕靖拍睢?br mpa-from-tpl="t">拓?fù)渑判蛞部梢酝ㄟ^ BFS 完成。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      unordered_map<int, unordered_set<int>> m;
      vector<int> indegree(numCourses, 0);
      for(auto& pre : prerequisites)
      {
        m[pre[1]].insert(pre[0]);
        indegree[pre[0]]++;
      }
      queue<int> q;
      int tp, finish = 0, i;
      for(i = 0; i < numCourses; ++i)
        if(indegree[i] == 0)
          q.push(i);
      vector<int> ans(numCourses);
      i = 0;
    while(!q.empty())
    {
      tp = q.front();
      finish++;
      ans[i++] = tp;
      q.pop();
      for(auto id : m[tp])
      {
        if(--indegree[id] == 0)
          q.push(id);
      }
    }
    if(i != numCourses)
      return {};
    return ans;
    }
};

class Solution {
    unordered_map<int, unordered_set<int>> m;
    vector<int> ans;
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
      for(auto& pre : prerequisites)
      {
            m[pre[1]].insert(pre[0]);
            indegree[pre[0]]++;
        }
        bool can = true;
        vector<int> visited(numCourses,0);
      for(int i = 0; i < numCourses; ++i)
        {
            if(indegree[i]==0)//從入度0的開始
                dfs(i, visited, can);
            if(!can)
                return {};
        }
        if(ans.size() < numCourses)//不夠個(gè)數(shù)，說明有的存在環(huán)
            return {};
        reverse(ans.begin(),ans.end());//反序
        return ans;
    }

    void dfs(int i, vector<int> & visited, bool &can)
    {
        if(!can) return;
        if(visited[i]==2) return;
        if(visited[i]==1)
        {
            can = false;
            return;
        }
        visited[i] = 1;//進(jìn)入的時(shí)候?yàn)?
        for(auto id : m[i])
            dfs(id, visited, can);
        visited[i] = 2;//出去的時(shí)候?yàn)?
        ans.push_back(i);//出去的時(shí)候push進(jìn)去，（這是最后做的）最終答案反序即可
    }
};