# Leetcode 207. Course Schedule

`class Solution {public:    bool canFinish(int n, vector<vector<int>>& prerequisites) {        buildGraph(n, prerequisites);        computeIndegrees(n);        for (int i = 0; i < n; ++i) {            int j = 0;            for (; j < n; ++j) {                //at least one has zero indegree                if (!degrees_[j]) break;            }            //no zero indegree nodes. It means we mush have cycles in the graph.            if (j == n) return false;            //if we can go here, it meas degrees_[j] is 0. The following will change it to -1.            --degrees_[j];            for (int &v : graph_[j]) --degrees_[v];        }        return true;    }private:    vector<vector<int>> graph_;    vector<int> degrees_;    void buildGraph(int n, vector<vector<int>>& prerequisites){         graph_.resize(n);        for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);    }        void computeIndegrees(int n) {        degrees_.resize(n);        for (auto &adj : graph_)             for (int &v : adj)                 ++degrees_[v];    }};`
`class Solution {public:    bool canFinish(int n, vector<vector<int>>& prerequisites) {        vector<vector<int>> G(n);        vector<int> degree(n, 0), bfs;        for (auto& e : prerequisites)            G[e[1]].push_back(e[0]), degree[e[0]]++;        for (int i = 0; i < n; ++i) if (!degree[i]) bfs.push_back(i);        for (int i = 0; i < bfs.size(); ++i)            for (int j: G[bfs[i]])                if (--degree[j] == 0) bfs.push_back(j);        return bfs.size() == n;    }    };`
`class Solution {public:    bool canFinish(int n, vector<vector<int>>& prerequisites) {        graph_.resize(n);        todo_.resize(n);        done_.resize(n);        buildGraph(n, prerequisites);        for (int i = 0; i < n; i++) {            if (!done_[i] &&!acyclic(i)){                return false;            }        }        return true;    }private:    vector<vector<int>> graph_;    vector<bool> todo_, done_;    unordered_set<int> this_seen_;        void buildGraph(int n, vector<vector<int>>& prerequisites) {        for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);    }       bool acyclic(int node) {        if (todo_[node]) {            return false;        }        if (done_[node]) {            return true;        }        todo_[node] = done_[node] = true;        for (int &v : graph_[node]) {            if (!acyclic(v)) {                return false;            }        }        todo_[node] = false;        return true;    }    };`
`class Solution {public:    bool canFinish(int n, vector<vector<int>>& prerequisites) {        graph_.resize(n);        todo_.resize(n);        done_.resize(n);        buildGraph(n, prerequisites);        for (int i = 0; i < n; i++) {            //if not explored. Explore it. If a cycle is detected, return false.            if (!done_[i] &&cyclic(i)){                return false;            }        }        return true;    }private:    vector<vector<int>> graph_;    vector<bool> todo_, done_;    unordered_set<int> this_seen_;        void buildGraph(int n, vector<vector<int>>& prerequisites) {        for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);    }       bool cyclic(int node) {       //if in this path, we go back to some visited node, then we detect a cycle.        if (todo_[node]) {            return true;        }       //for this path, if we reach to a done node, then the exploration process is ended. And no cycle will be detected as if we do have cycles, the program will be terminated by previous code.        if (done_[node]) {            return false;        }       // set both todo and done as true. Done means we explored this node globally.       // todo is only for this dfs path. This dfs is a local path.         todo_[node] = done_[node] = true;        for (int &v : graph_[node]) {            if (cyclic(v)) {                return true;            }        }        todo_[node] = false;        return false;    }    };`
`/*       //after dfs, the local path should be set as unvisited as other local path may use this node.       // such as                 1       //                0                  3       //                         2       // If 0->1, 1->3, 0->2 and 2->3, when we explore node 0, we will have two paths       //1) path 013        // the changing process of todo and done will be       // node 0: todo {0:true, 1:false,2:false,3:false },done {0:true, 1:false,2:false,3:false }       // node 1: todo {0:true, 1:true,2:false,3:false },done {0:true, 1:true,2:false,3:false }       // node 3:todo {0:true, 1:true,2:false ,3:true},done {0:true, 1:true,2:false,3:true}       // after visit node3, we touch the bottom of the path, and we will set todo[node] back to false       // we get dfs(3)=false, and       //todo {0:true, 1:true,2:false ,3:false},done {0:true, 1:true,2:false,3:true}       // then we get dfs(1)=false and       //todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}       // then dfs(0) fasle       ////todo {0:false, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}       //2) path 023.       node 0: todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}       node 2: todo {0:true, 1:false,2:true ,3:false},done {0:true, 1:true,2:true,3:true}       node 3: as done[3] is true, we can get dfs(3) is true immediate.       todo {0:true, 1:false,2:true ,3:false},done {0:true, 1:true,2:true,3:true}       then dfs(2) is true       todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:true,3:true}       then dfs(0) is true       todo {0:false, 1:false,2:false ,3:false},done {0:true, 1:true,2:true,3:true}       DONE.       */`

# 269. Alien Dictionary

`class Solution {public:    string alienOrder(vector<string>& words) {        if (words.size() == 0) return "";        unordered_map<char, int> indegree;        unordered_map<char, unordered_set<char>> graph;                // initialize        for (int i = 0; i < words.size(); i++) {            for (int j = 0; j < words[i].size(); j++) {                char c = words[i][j];                indegree[c] = 0;             }        }                // build graph and record indegree        for (int i = 0; i < words.size() - 1; i++) {            string cur = words[i];            string nex = words[i + 1];            int len = min(cur.size(), nex.size());            for (int j = 0; j < len; j++) {                if (cur[j] != nex[j]) {                    unordered_set<char> set = graph[cur[j]];                    if (set.find(nex[j]) == set.end()) {                        graph[cur[j]].insert(nex[j]); // build graph                        indegree[nex[j]]++; // add indegree                    }                    break;                                        }            }        }                // topoligical sort        string ans;        queue<char> q;        for (auto& e : indegree) {            if (e.second == 0) {                q.push(e.first);            }        }        while(!q.empty()) {            char cur = q.front();            q.pop();            ans += cur;                        if (graph[cur].size() != 0) {                for (auto& e : graph[cur]) {                    indegree[e]--;                    if (indegree[e] == 0) {                        q.push(e);                    }                }            }                    }                // tell if it is cyclic        return ans.length() == indegree.size() ? ans : "";    }};`
`class Solution {public:    string alienOrder(vector<string>& words) {        if (words.size()==0)return "";        unordered_map<char, int>  degree;        unordered_map<char, unordered_set<char>> graph;                // initialize        for (auto & word: words)            for (auto& w : word)                degree[w] = 0;        //build graph        for (int i =0; i<words.size()-1;++i){            string cur = words[i], nxt = words[i+1];            for (int j=0;j<min(cur.size(), nxt.size());++j){                if(cur[j]!=nxt[j]){                    char w1 = cur[j], w2 = nxt[j];                    auto it = graph[w1].find(w2);                    if(it==graph[w1].end()){                        graph[w1].insert(w2);                        degree[w2]++;                    }                    break;                }            }        }                //top sort        queue<char> q;        for (auto &v: degree){            if(v.second==0)q.push(v.first);        }        string res;        while(!q.empty()){            char ch = q.front();            res+= ch;            q.pop();            for(auto &j:graph[ch]){                if(--degree[j]==0){                    q.push(j);                }            }                    }        return res.size()==degree.size()?res:"";    }};`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi