Three different solutions in C, well-commented


  • 1

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

Log in to reply
 

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