# Very intuitive solution turning this problem into a graph traversing accepted in C, well-explained

• To find a permutation that can meet the inter-dependent constraints which will simply remind us of the graph traversal problem.

searching for circle in the graph which in this problem will means dead-lock -> impossible -> false.

To hack this one we will need the following two steps:

• since the prerequisites are end -> begin sequence, we need to turn it to begin -> end sequence just like a graph -> turning the prerequisites to a graph -> list of edge pairs for latter traversal ;
• traverse from each node and labeled it as visited and then using DFS to traverse further to find whether there is a circle in the graph.

Two tricks to accelerate the searching process:

• after each traversal (start from one node) check the flag isCycle and if it's true just return avoid further searching;

• using three different states to label the node visited 0 for not-visited, 1 for visited in the current searching path, 2 for visited before trying to avoid starting the searching from this point again since it's traversed.

• space cost O(E*V) E -> the amount of edges, V -> the amount of vertexes;

• time cost O(E*V) since there are many pruning operations, the cost will be dramatically reduced.

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

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