BFS 3 - Topological Sorting

1. Course Schedule II

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, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example
Given n = 4, prerequisites = [1,0],[2,0],[3,1],[3,2]]
Return [0,1,2,3] or [0,2,1,3]

拓扑排序

vector<int> findOrder(int numCourses, vector<pair<int, int>> &prerequisites) {
    vector<int> result;
    if(numCourses <= 0) return result;
    // 1. 存入度 和 链接关系
    unordered_map<int, int> indus;
    unordered_map<int, vector<int>> neighbors;
    for(auto node: prerequisites) {
        indus[node.first]++;
        neighbors[node.second].push_back(node.first);
    }
    // 2. 找出为0的点，可以开始
    queue<int> q;
    for(int i=0; i<numCourses; i++) {
        if(indus.find(i) == indus.end()) {
            q.push(i);
        }
    }
    // 3. BFS遍历，存出来结果
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        result.push_back(cur);
        for(auto n: neighbors[cur]) {
            // 减少入度，为0才访问，所以不需要visited，只可能放进去1次
            if(--indus[n] == 0) q.push(n);
        }
    }
    if(result.size() < numCourses) return vector<int>();
    return result;
}

2. Topological Sorting

假设图中至少存在一种拓扑排序

vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
    vector<DirectedGraphNode*> result;
    if(graph.empty()) return result;
    // 1. 存入度
    unordered_map<DirectedGraphNode*, int> indus;
    queue<DirectedGraphNode*> q;
    for(auto node: graph) {
        for(auto n: node->neighbors) {
            if(indus.find(n) == indus.end()) indus[n] = 1;
            else indus[n]++;
        }
    }
    // 2. 找出为0的点，可以开始
    // unordered_set<DirectedGraphNode*> visited;
    for(auto node: graph) {
        if(indus.find(node) == indus.end()) {
            q.push(node);
            // visited.insert(node);  // 假设图中至少存在一种拓扑排序=>有向无环图，不需要visited，而且只有减到0才放，肯定只放1次
        }
    }
    // 3. BFS遍历，存出来结果
    while(!q.empty()) {
        DirectedGraphNode* cur = q.front();
        q.pop();
        result.push_back(cur);
        for(auto n: cur->neighbors) {
            // 减少入度，为0则访问
            if(--indus[n] == 0) {
                q.push(n);
                // visited.insert(n);
            }
        }
    }
    return result;
}