Topological Sort

Kahn’s Algorithm

Find the node with zero indegrees.
Remove it, and reduce it’s neighbours indegrees as well

Now if any neighbour had indegree = 0 after subtracting, add it to the queue
Verified here: https://www.geeksforgeeks.org/problems/topological-sort/1

class Solution {
  public:
    vector<int> topoSort(int v, vector<vector<int>>& edges) {
        // calculate the indegree of all the nodes
        vector<int> indeg(v, 0);
        vector<vector<int>> adj(v);
        for (auto edge: edges) {
            int from = edge[0];
            int to = edge[1];
            indeg[to]++;
            adj[from].push_back(to);
        }
        
        queue<int> queue;
        for (int i = 0; i < v; i++) {
            if (indeg[i] == 0) {
                queue.push(i);
            }
        }
        
        vector<int> topoSorted;
        while(!queue.empty()) {
            int cur = queue.front();
            queue.pop();
            topoSorted.push_back(cur);
            for (auto next: adj[cur]) {
                indeg[next]--;
                if (indeg[next] == 0) {
                    queue.push(next);
                }
            }
        }
        return topoSorted;
    }
};

Alien Dictionary

Beautiful Problem.
Find the first character that’s different and build the graph based on that.
Use that to topo sort.
Verified here: https://www.geeksforgeeks.org/problems/alien-dictionary/1

class Solution {
  public:
    string findOrder(vector<string> &words) {
        // code here
        // to create the dependency
        // so compare each word to it's neighbour and 
        // find the first different character
        // use that to create the adj graph
        int numWords = words.size();
        map<char, vector<char>> dep;
        map<char, int> indeg;
        for (auto word: words) {
            for (auto ch: word) {
                dep[ch] = {};
                indeg[ch] = 0;
            }
        }
        for (int i = 0; i+1 < words.size(); i++) {
            string word1 = words[i];
            string word2 = words[i+1];
            int ptr1 = 0;
            int ptr2 = 0;
            bool diff = false;
            while(ptr1 < word1.size() && ptr2 < word2.size()) {
                if (word1[ptr1] != word2[ptr2]) {
                    diff = true;
                    break;
                }
                ptr1++;
                ptr2++;
            }
            if (!diff && word1.size() > word2.size()) {
                return "";
            }
            if (diff) {
                indeg[word2[ptr2]]++;
                dep[word1[ptr1]].push_back(word2[ptr2]);
            }
        }
        queue<char> q;
        for (auto &[ch, cnt]: indeg) {
            if (cnt == 0) {
                q.push(ch);
            }
        }
        string order = "";
        while(!q.empty()){
            char cur = q.front();
            order += cur;
            q.pop();
            for (auto next: dep[cur]) {
                indeg[next]--;
                if (indeg[next] == 0) {
                    q.push(next);
                }
            }
        }
        return order.size() == indeg.size() ? order : "";
    }
};