258ms cpp solution by using vector to represent a graph, and bfs to solve the problem


  • 0
    O
    class Solution {
    public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
    	int n = prerequisites.size();
    	if(n * numCourses == 0)
    		return true;
    	stack<int> zero;
    	vector<int> inDegree(numCourses, 0);
    	vector<vector<int> > graph(numCourses, vector<int>(0, 0));
    	for(int i = 0; i < n; i++)
    	{
    		int pre = prerequisites[i][0];
    		int after = prerequisites[i][1];
    		graph[pre].push_back(after);
    		inDegree[after]++;
    	}
    	for(int i = 0; i < numCourses; i++)
    		if(inDegree[i] == 0)
    			zero.push(i);
    	while(!zero.empty())
    	{
    		int take = zero.top();
    		zero.pop();
    		for(int i = 0; i < graph[take].size(); i++)
    		{
    			int after = graph[take][i];
    			inDegree[after]--;
    			if(inDegree[after] == 0)
    				zero.push(after);
    		}
    	}
    	for(int i = 0; i < numCourses; i++)
    		if(inDegree[i] != 0)
    			return false;
    	return true;
    }
    };

  • 0
    W

    It's amazing we almost share the same code. While there is no need to check the vector inDegree to find whether there exists left edges. Here, we can use the var n.

    In the while loop, when you do the operation inDegree[after]--;, we make --n;

    After the while loop, we just check whether n is zero or not. It not, there must have a cycle.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.