[leetcode 207] Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take.   To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: 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.

 

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

풀이:

결국 그래프 내에서 사이클이 존재하면 안된다는 의미가 된다. 서로가 선수과목이라면 모든 과목을 수강할 수 없기 때문.

그래프내에서 사이클을 찾는 kahn 알고리즘을 사용한다.

eazymean.tistory.com/113

[알고리즘] Directed Graph에서 사이클 찾기(미완성)

class Solution {
public:
    vector<int> v[100001];
   
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int inDegree[10001]={0,};
        for(int i=0; i<prerequisites.size(); i++){
            
            int root = prerequisites[i][0];
            int node = prerequisites[i][1];
            
            v[root].push_back(node);
            inDegree[node]++;
        }
        
        queue<int> q; //push start node
        for(int i=0; i<numCourses; i++){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        
        
        while(!q.empty()){
            int fr = q.front();
            q.pop();
            
            for(int i=0; i<v[fr].size(); i++){
                if(--inDegree[v[fr][i]] == 0){
                    q.push(v[fr][i]);
                }
            }
        }
        
        for(int i=0; i<numCourses; i++){
            if(inDegree[i] > 0){
                return false;
            }
        }
            
        return true;
    }
};