力扣(LeetCode)207.课程表(C++)-创新互联

根据示例看出，课程表是否存在环，是问题的关键。这题的环，和数组、链表的环不一样，不好判，要转化成图判拓扑序列。

考虑向右和向左的方向，拓扑序列的所有边可以指向同一方向。

无环图进行重排序，以及延展后，可以生成拓扑序列。考虑有环的性质 : 即使环外的边已经有序，环内至少有一条边是反向的，无法生成拓扑序列。

拓扑排序 : 队列里维护可以构造拓扑序列的点，每次将入度 ① _① ①​ 为 0 0 0 的点入队(在图中删除)，相邻点的入度减一。如果有环的话，由于环的路径依赖，环内所有点都会有一个无法删除的前驱(入度至少为 1 1 1 )，这些点无法入队。完成拓扑排序后，如果所有点入队，则无环，否则有环。

①入度 : 对于有向图的某个点，箭头指向这个点的边数，就是这个点的入度。

• d d d 保存所有点的入度。
• g g g 保存所有点的出边，便于在删除某个点之后，维护这个点的出边的入度

• 没入队的某些点形成了环。
• 如果所有点入队，队列维护的点的顺序，刚好组成图的一个拓扑序列(不唯一）

class Solution {public:
    bool canFinish(int n, vector>& p) {vector>g(n);
        vectord(n);
        for(auto &e:p) {g[e[1]].push_back(e[0]);
            d[e[0]]++;
        }
        queueq;
        for(int i = 0;iauto edge = q.front();
            q.pop();
            for(auto &e:g[edge])
                if(0==--d[e])
                    q.push(e);
            ans++;
        }
        return ans == n;
    }
};

1. 时间复杂度 : O ( n + m ) O(n+m) O(n+m) ， n n n 是有向图的结点数， m m m 是边数，无环图要遍历所有点和邻边，时间复杂度 O ( n + m ) O(n+m) O(n+m) 。
2. 空间复杂度 : O ( n + m ) O(n+m) O(n+m) ， 维护入度和出边的数组，空间复杂度 O ( n + m ) O(n+m) O(n+m) ，队列的最坏空间复杂度 O ( n ) O(n) O(n)，总体空间复杂度 O ( n + m ) O(n+m) O(n+m) 。

• 理解思路很重要！
• 欢迎读者在评论区留言，墨染看到就会回复的。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧