Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

解析：

判断一个有向图是否存在环，利用BFS，把所有入度为0的点放入栈中，再把其相连的点的入度-1，并判断入度是否变为0，如果是0进栈。

代码：

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
      
      
      vector<vector<int>>graph(numCourses);
      vector<int>in(numCourses,0);
      for (int i=0; i<prerequisites.size(); i++)
      {
          graph[prerequisites[i].first].push_back(prerequisites[i].second);
          in[prerequisites[i].second]++;
      }
      
      
      queue<int>q;
      for (int i=0; i<numCourses; i++)
      {
          if (in[i]==0)
          q.push(i);
      }
      
      while(!q.empty())
      {
          int temp=q.front();
          q.pop();
          
          for (int i=0; i<graph[temp].size(); i++)
          {
              in[graph[temp][i]]--;
              if (in[graph[temp][i]]==0)
              {
                  q.push(graph[temp][i]);
              }
          }
      }
      
      
      for (int i=0; i<numCourses; i++)
      {
          if (in[i]!=0)
          return false;
      }
       
        return true;
        
        
    }
};