Binary Search Tree Iterator(中序遍历)

题目

题意

给定一些课程和每门课对应的若干先修课程，要求必须修完对应先修课程才能修这门课，问是否存在一种修课顺序，能够修完所有的课。

分析

这本质上就是一个在有向图中寻找拓扑序的问题，对于有向图的拓扑排序，有两种思路：

一种时利用深度优先遍历，其节点访问顺序的就是一种拓扑排序的顺序，其利用的是出度为0的特点
第二种将入度为0的节点入栈，如此往复，直至所有节点都入栈，这是利用了入度为0的特点

无论采取哪种方法，其基本思路都是利用拓扑排序的基本特征结合我们常用的数据结构所得的产物。

代码

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (numCourses <= 1)
            return true;

        vector<vector<int>> graph;
        int in[numCourses];  // 入度
        for (int i = 0; i < numCourses; i++) {
            in[i] = 0;
            vector<int> t;
            graph.push_back(t);
        }

        // [0, 1]: 1 -> 0
        for (int i = 0; i < prerequisites.size(); i++) {
            int x = prerequisites[i].first;
            int y = prerequisites[i].second;
            in[x]++;
            graph[y].push_back(x);
        }

        // 暂时不做堆优化，直接暴力
        int finished = 0;
        while (finished < numCourses) {
            int found = -1;
            for (int i = 0; i < numCourses; i++)
                if (in[i] == 0) {
                    found = i;
                    break;
                }
            if (found == -1)
                return false;
            for (int j = 0; j < graph[found].size(); j++)
                in[graph[found][j]]--;
            in[found] = -1;
            finished++;
        }
        return true;
    }
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com