Topological sort

If you are not clear about what is topological sort, please google and Wikipedia it first.

We can use DFS to achieve topological sort. Also, BFS can be used to solve topological sort.

Leetcode 207. Course Schedule

Course Schedule - LeetCode

Reference

https://leetcode.com/problems/course-schedule/discuss/58509/C++-BFSDFS

BFS

“ BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise, we set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of its neighbors by 1. This process will be repeated for n (number of nodes) times.”

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];
    }
};

Or we can have a more concise one from lee215

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;
    }
    
};

“For DFS, in each visit, we start from a node and keep visiting its neighbors, if at a time we return to a visited node, there is a cycle. Otherwise, start again from another unvisited node and repeat this process. We use todo and done for nodes to visit and visited nodes.”

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;
    }
    
};

Change the logic from not a cycle to cyclic.

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;
    }
    
};

explain step by step can be found here.

/*
       //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

https://leetcode.com/problems/alien-dictionary/

https://leetcode.com/problems/alien-dictionary/discuss/157298/C++-BFS-and-Topoligical-Sort-with-explanation

BFS + Topological Sort, time complexity O(n), space complexity O(n)

STEP 1: Initialize
for each letter in each word indegree[letter] = 0;

STEP 2: Build Graph and Record the edge
for each edge (cur node, nex node) graph.insert(cur, nex)
for each nex node indegree[nex]++;

STEP 3: Topological Sort
use queue, push all nodes which indegree is 0;
use BFS start to iterate the whole graph.

STEP 4: Tell if cyclic
compare the result with indegree if (res.size() == indegree.size());

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 : "";
    }
};

Rewritten it to my owner version

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:"";
    }
};

Above code is based on BFS? Can we implement one based on DFS?