# Leetcode刷題學習筆記 -- Topological Sorting
## Introduction
[Kahn's Algorithm for Topological Sorting](https://leetcode.com/explore/featured/card/graph/623/kahns-algorithm-for-topological-sorting/)
In-Degree : 連到這個node的個數。
Out-Degree : 從這個node連出去的個數。

### [210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> need(numCourses);
    unordered_map<int, vector<int>> m;
    for(auto& req : prerequisites) {
        need[req[0]]++;
        m[req[1]].push_back(req[0]);
    }
    vector<int> rtn;
    queue<int> q;
    for(int i = 0; i < numCourses; ++i) {
        if(need[i] == 0) q.push(i);
    }
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        rtn.push_back(cur);
        for(auto& nxt : m[cur]) {
            if(--need[nxt] == 0)
                q.push(nxt);
        }
    }
    return rtn.size() == numCourses ? rtn : vector<int>();
}

### [802. Find Eventual Safe States](https://leetcode.com/problems/find-eventual-safe-states/)

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int sz = graph.size();
    vector<vector<int>> from(sz, vector<int>());
    vector<int> out(sz);
    vector<int> rtn;
    queue<int> q;
    for(int i = 0; i < sz; ++i) {
        out[i] = graph[i].size();
        if(out[i] == 0) { 
            q.push(i);
            rtn.push_back(i);
        }
        for(int j = 0; j < out[i]; ++j)
            from[graph[i][j]].push_back(i);
    }
    while(!q.empty()) {
        for(int i = q.size(); i > 0; --i) {
            int n = q.front(); q.pop();
            for(auto& next : from[n]) {
                out[next]--;
                if(out[next] == 0) {
                    q.push(next);
                    rtn.push_back(next);
                }
            }
        }
    }
    sort(rtn.begin(), rtn.end());
    return rtn;
}

###### tags: `leetcode` `刷題`