【leetcode】Course Schedule（middle）☆

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

思路：

把课程序号做顶点，把给定的对作为边，就是找图里有没有环。

我自己代码：

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        bool hasCircle = false;
        
        vector<vector<int>> edges(numCourses); //换一种表示图的方式 edges[0]表示顶点0对应的边 后面是所有它指向的顶点
        for(int i = 0; i < prerequisites.size(); ++i)
            edges[prerequisites[i].first].push_back(prerequisites[i].second);

        bool * isusedv = (bool *)calloc(numCourses, sizeof(bool)); //存储顶点是否使用过
        for(int i = 0; i < prerequisites.size(); ++i)
        {
            hasCircle = findCircle(edges, isusedv, prerequisites[i].first);
            if(hasCircle) break;
        }
　　　　 free(isusedv);
        return !hasCircle;
    }

    bool findCircle(vector<vector<int>> &edges, bool * isusedv, int vid) //DFS
    {
        if(isusedv[vid])
            return true;  //找到了圈
        isusedv[vid] = true; //标记该节点为用过
        bool hasCircle = false;
        for(int i = 0; i < edges[vid].size(); ++i)
        {
            hasCircle |= findCircle(edges, isusedv, edges[vid][i]);
            if(hasCircle) break; //一旦找到了圈就返回
        }
        isusedv[vid] = false;
        return hasCircle;
    }

大神的代码：

BFS拓扑排序：

一个简单的求拓扑排序的算法：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
    vector<unordered_set<int>> matrix(numCourses); // save this directed graph
    for(int i = 0; i < prerequisites.size(); ++ i)
        matrix[prerequisites[i][1]].insert(prerequisites[i][0]);

    vector<int> d(numCourses, 0); // in-degree
    for(int i = 0; i < numCourses; ++ i)
        for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
            ++ d[*it];

    for(int j = 0, i; j < numCourses; ++ j)
    {
        for(i = 0; i < numCourses && d[i] != 0; ++ i); // find a node whose in-degree is 0

        if(i == numCourses) // if not find
            return false;

        d[i] = -1;
        for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
            -- d[*it];
    }

    return true;
}

DFS找环

bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
    vector<unordered_set<int>> matrix(numCourses); // save this directed graph
    for(int i = 0; i < prerequisites.size(); ++ i)
        matrix[prerequisites[i][1]].insert(prerequisites[i][0]);

    unordered_set<int> visited;
    vector<bool> flag(numCourses, false);
    for(int i = 0; i < numCourses; ++ i)
        if(!flag[i])
            if(DFS(matrix, visited, i, flag))
                return false;
    return true;
}
bool DFS(vector<unordered_set<int>> &matrix, unordered_set<int> &visited, int b, vector<bool> &flag)
{
    flag[b] = true;
    visited.insert(b);
    for(auto it = matrix[b].begin(); it != matrix[b].end(); ++ it)
        if(visited.find(*it) != visited.end() || DFS(matrix, visited, *it, flag))
            return true;
    visited.erase(b);
    return false;
}