136ms Solution Topological Sort


  • 0
    P
    public:
    bool canFinish(int numCourses, std::vector<std::pair<int, int>>& prerequisites) {
    	bool **pMatrix = (bool **)malloc(sizeof(bool *) * numCourses);
    	for(int i = 0; i < numCourses; ++i)
    	{
    		pMatrix[i] = (bool *)malloc(sizeof(bool) * numCourses);
    		memset(pMatrix[i], 0, sizeof(bool) * numCourses);
    	}
    
    	int nSize = prerequisites.size();
    	for(int i = 0; i < nSize; ++i)
    	{
    		pMatrix[prerequisites[i].first][prerequisites[i].second] = true;
    	}
    
    	int *pVec = (int *)malloc(sizeof(int) * numCourses);
    
    	for(int i = 0; i < numCourses; ++i)
    	{
    		int nCount = 0;
    		for(int j = 0; j < numCourses; ++j)
    		{
    			if(pMatrix[i][j])
    			{
    				++nCount;
    			}
    		}
    		pVec[i] = nCount;
    	}
    
    	int nIndex = -1;
    	for(int i = 0; i < numCourses; ++i)
    	{
    		if(pVec[i] == 0)
    		{
    			nIndex = i;
    		}
    	}
    
    	while(nIndex >= 0)
    	{
    		int nTmpIndex = -1;
    		pVec[nIndex] = -1;
    		for(int i = 0; i < numCourses; ++i)
    		{
    			if(pMatrix[i][nIndex])
    			{
    				--pVec[i];
    			}
    
    			if(pVec[i] == 0 && nTmpIndex == -1)
    			{
    				nTmpIndex = i;
    			}
    		}
    		nIndex = nTmpIndex;
    	}
    
    	for(int i = 0; i < numCourses; ++i)
    	{
    		if(pVec[i] >= 0)
    		{
    			return false;
    		}
    	}
    	return true;
    }

Log in to reply
 

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