# Three different solutions in C, well-commented

• The first solution is to use DFS to traverse until there is a cycle within the graph then return false otherwise it can be visited without cycle -> return true.

``````void traverse(int start, int** graph, int* colSize, int* visited, bool* isCycle)
{
if(visited[start] == 1) { *isCycle = true; return ; }
visited[start] = 1;
for(int i = 0; i < colSize[start]; i++)
{
traverse(graph[start][i], graph, colSize, visited, isCycle);
if(*isCycle) return ;
}
visited[start] = 2;
}
bool canFinish(int courses, int** prerequisites, int rSize, int cSize)
{
int space = sizeof(int)*courses;
int* colSize = (int*)malloc(space); //count of edges of a certain node;
memset(colSize, 0, space);
int** graph = (int**)malloc(sizeof(int*)*courses); //constructing the graph;
for(int i = 0; i < courses; i++)
graph[i] = (int*)malloc(sizeof(int)*2);
for(int r = 0; r < rSize; r++)
{
int num = prerequisites[r][1]; //the head of the edge;
colSize[num]++;
graph[num][colSize[num]-1] = prerequisites[r][0];
}
int *visited = (int*)malloc(space);
memset(visited, 0, space);
bool isCycle = false;
for(int i = 0; i < courses; i++)
{
if(isCycle) return false;
if(visited[i] == 0) traverse(i, graph, colSize, visited, &isCycle);
}
return !isCycle;
}
``````

The next two solutions are to take advantage of topology sort to check whether there is a cycle or not, while the first solution is to construct a graph first which is represented by EdgeList, the second is searching directly in the given prerequisites which is of course a little bit slower compared to the first one but saving space cost.

V - the amount of vertexes; E - the amount of edges;

The first solution:

• time cost O(V^2)
• space cost O(V^2)

The second solution:

• time cost O(EV)
• space cost O(V)

``````bool canFinish(int courses, int** prerequisites, int rSize, int cSize)
{
int* colSize = (int*)malloc(sizeof(int)*courses); //count of edges of a certain node;
memset(colSize, 0, sizeof(int)*courses);
int** graph = (int**)malloc(sizeof(int*)*courses); //constructing the graph;
for(int i = 0; i < courses; i++)
graph[i] = (int*)malloc(sizeof(int)*courses);
for(int r = 0; r < rSize; r++)
{
int num = prerequisites[r][1]; //the head of the edge;
colSize[num]++;
graph[num][colSize[num]-1] = prerequisites[r][0];
}
int *degrees = (int*)malloc(sizeof(int)*courses);
for(int i = 0; i < courses; i++) //get the in-degree for each node;
for(int j = 0; j < colSize[i]; j++)
degrees[graph[i][j]]++;
for(int i = 0; i < courses; i++) //topological sort;
{
int j = 0;
for(; j < courses; j++) //searching for the in-degree-0 node;
if(degrees[j] == 0) break;
if(j == courses) return false; //no such node;
degrees[j] = -1; //set it invalid;
for(int k = 0; k < colSize[j]; k++) degrees[graph[j][k]]--;
}
return true;
}
``````

``````bool canFinish(int courses, int** prerequisites, int rSize, int cSize)
{
int *degrees = (int*)malloc(sizeof(int)*courses);
memset(degrees, 0, sizeof(int)*courses);
for(int r = 0; r < rSize; r++)
degrees[prerequisites[r][0]]++;
for(int i = 0; i < courses; i++) //topological sort;
{
int j = 0;
for(; j < courses; j++) //searching for the in-degree-0 node;
if(degrees[j] == 0) break;
if(j == courses) return false; //no such node;
degrees[j] = -1; //set it invalid;
for(int k = 0; k < rSize; k++)  //topology sort;
if(prerequisites[k][1] == j) //only the current node is the head of the edge;
degrees[prerequisites[k][0]]--;
}
return true;
}``````

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