# 136ms Solution Topological Sort

• ``````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;
}``````

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