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


  • 0

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

Log in to reply
 

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