LeetCode Q207: 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.

Solution:

Topological sort

	class Solution {
	public:
	struct Node{
	vector<int> isPreOf;
	void addPre(int preIdx){
	isPreOf.push_back(preIdx);
	}
	};
	bool canFinish(int n, vector<pair<int, int>>& pre) {
	vector<Node> graphs(n);
	vector<int> dependLeft(n, 0);
	for(int i=0; i<pre.size(); i++){
	pair<int, int> p=pre[i];
	dependLeft[p.first]+=1;
	graphs[p.second].addPre(p.first);
	}
	for(int i=0; i<pre.size(); i++){
	int c=-1;
	int d=0;
	for(int j=0; j<n; j++){
	if(dependLeft[j]==0){
	dependLeft[j]=-1;
	c=j;
	break;
	}
	if(dependLeft[j]==-1)
	d++;
	}
	if(d==n)
	return true;
	if(c==-1)
	return false;
	for(int j=0; j<graphs[c].isPreOf.size(); j++){
	dependLeft[graphs[c].isPreOf[j]]-=1;
	}
	}
	}
	};

view raw Q207CourseSchedule.cpp hosted with ❤ by GitHub