Why my c++ solution TLE?


  • 0
    H
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    	vector<int> temp(numCourses, 1);
    	for (int i = 0; i < prerequisites.size(); i++) {
    		temp[prerequisites[i][0]] = 0;
    	}
    
    	vector<vector<int>> newEdges;
    	vector<vector<int>> removedEdges;
    	for (int e = 0; e < prerequisites.size(); e++) {
    		if (temp[prerequisites[e][1]] == 0)
    			newEdges.push_back(prerequisites[e]);
    		else
    			removedEdges.push_back(prerequisites[e]);
    	}
    
    	while (!removedEdges.empty()) {
    		for (int i = 0; i < numCourses; i++)
    			temp[i] = 1;
    		for (int i = 0; i < newEdges.size(); i++)
    			temp[newEdges[i][0]] = 0;
    		vector<vector<int>> tempEdges;
    		removedEdges.clear();
    		for (int e = 0; e < newEdges.size(); e++) {
    			if (temp[newEdges[e][1]] == 0)
    				tempEdges.push_back(newEdges[e]);
    			else
    				removedEdges.push_back(newEdges[e]);
    		}
    		newEdges.clear();
    		newEdges.insert(newEdges.begin(), tempEdges.begin(), tempEdges.end());
    	}
    	if (newEdges.empty())
    		return true;
    	return false;
    }
    

    On my machine, it cost 192ms.
    And I run another one's accepted code, it got 120ms or 228ms.

    My solution is based on Topological Sort, it removes all nodes which indegree is 0 in every round, and end in when there is no removedEdges.


Log in to reply
 

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