changed a year ago  
Published Linked with GitHub

Leetcode刷題學習筆記 – Topological Sorting

Why Topological Sorting?

  • 有向圖。
  • 先處理indegree為0的node
  • 當indegree不為0，表示還有其他路徑還沒到達這個node。
  • 如果有cycle，處理過的node個數就不會等於總數。

因為可以從相依性為0的node開始，一層一層像剝洋蔥一樣，把圖剝開來，讓問題有個好的解決順序。

Introduction

Topological sort是針對有向圖，從indegree為零的點開始，因為indegree = 0表示沒有相依性。
如下圖:

ts1

其中四個點沒有相依性(indegree = 0)，為[t, x, w, q]
拿掉這四個點之後，同時也跟新這四個點的child，減少child的indegree數值。

ts2

這時可以發現indegree = 0的node為[c, h, m]。再拿掉這三個點，可以得到以下的圖。

ts3

時可以發現indegree = 0的node為[k, g]。再拿掉這兩個點，可以得到以下的圖。

ts4

最後剩下[d, j]這兩個點。

偵測cyclic

  • 使用topological sorting，最後沒辦法拿掉的node，就是cyclic graph。因為indegree不會為0。

統計chains的長度

  • 一層一層拿掉node，就可以統計這條chain到底多長。按照題目，可以找出最長的chain或是找出串接node的數量。







// 找出最長的chain
vector<int> len(sz, 1);
while(!q.empty()) {
    int c = q.front(); q.pop();
    int n = next[c];
    len[n] = max(len[n], len[c] + 1);
}








// 找出chain上全部的node數
vector<int> len(sz, 1);
while(!q.empty()) {
    int c = q.front(); q.pop();
    for(auto&n : next[c])
        len[n] += len[c];
}

Code Snippet

1. 統計indegree





vector<int> in(sz);
for(int i = 0; i < sz; ++i) {
    in[edges[i]]++;
}

2. 把indegree為0的放進queue






queue<int> q;
for(int i = 0; i < sz; ++i) {
    if(in[i] == 0)
        q.push(i);
}

3.反覆刪除indegree為0的node，直到沒這樣的node為止。







while(!q.empty()) {
    int cur = q.fornt(); q.pop();
    int& n = edges[cur];
    in[n]--;
    if(in[n] == 0) q.push(n);
}

Problems

210. Course Schedule II






































class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> need(numCourses);
        unordered_map<int, vector<int>> m;
        unordered_set<int> v;
        for(auto& req : prerequisites) {
            m[req[1]].push_back(req[0]);
            need[req[0]]++;
        }
        
        vector<int> ans;
        queue<int> q;
        for(int i = 0; i < numCourses; ++i) {
            if(need[i] == 0) {
                q.push(i);
                v.insert(i);
            }
        }
        
        while(!q.empty()) {
            int n = q.front(); q.pop();
            ans.push_back(n);
            
            for(auto& next : m[n]) {
                need[next]--;
                if(need[next] == 0 && !v.count(next)) {
                    q.push(next);
                    v.insert(next);
                }
            }
        }
        
        // 檢查是否有cyclic的情況
        return ans.size() == numCourses ? ans : vector<int>();
    }
};

329. Longest Increasing Path in a Matrix

找出矩陣中最長的遞增序列。

  1. 建立indegree和adj來使用topological sort。其中把2D的index轉換成1D的。








































class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int sz = m * n;
        vector<int> dirs{0, 1, 0, -1, 0};
        vector<int> ind(sz);
        unordered_map<int, vector<int>> adj;
        for(int y = 0; y < m; ++y) {
            for(int x = 0; x < n; ++x) {
                for(int i = 0; i < 4; ++i) {
                    int ny = y + dirs[i];
                    int nx = x + dirs[i + 1];
                    if(ny < 0 || nx < 0 || ny == m || nx == n ||
                        matrix[y][x] >= matrix[ny][nx]) continue;
                    ind[ny * n + nx]++;
                    adj[y * n + x].push_back(ny * n + nx);
                }
            }
        }

        int ans{0};
        queue<int> q;
        for(int i = 0; i < ind.size(); ++i) {
            if(ind[i] == 0) q.push(i);
        }

        while(!q.empty()) {
            for(int loop = q.size(); loop > 0; --loop) {
                int cur = q.front(); q.pop();
                for(auto& n : adj[cur]) {
                    if(--ind[n] == 0) q.push(n);
                }
            }
            ans++;
        }
        return ans;
    }
};

269. Alien Dictionary

給你一個vector<string> 其中的word是字典排序。但是字母的順序不是一般人類使用的a-z順序，而是alien使用的順序。試輸出使用此排序的string。

  1. 因為字母有前後順序，可以視為有向圖。
  2. indegree為0的字母一定是最前面的字母，所以可以使用topological sorting。
  3. 這邊要注意的是，如果下一個word是前一個word的prefix，這種狀況不可能成立，所以返回空字串。例如: "abc","ab"。照字典排列，"ab"應該會在"abc"前面。



// 檢查是否後面的string是否為前面的prefix
if(p.size() > c.size() && 
    p.substr(0, c.size()) == c) return "";
  1. 另外比到不一樣的char一定要break，因為後面已經沒參考價值。只是必須注意是否以前已經存過，避免indegree錯誤。









for(int j = 0; j < min(p.size(), c.size()); ++j) {
    if(p[j] != c[j]) {
        if(!adj[p[j]].count(c[j])){ // 檢查是否已經存過
            ind[c[j]]++;
            adj[p[j]].insert(c[j]);
        }
        break; // 不一樣就一定要break
    }
}

完整解答








































class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, int> ind;
        unordered_map<char, unordered_set<char>> adj;
        for(auto& w : words) {
            for(auto& c : w) ind[c] = 0;
        }
        
        for(int i = 1; i < words.size(); ++i) {
            string& p = words[i - 1], c = words[i];
            if(p.size() > c.size() && p.substr(0, c.size()) == c) return "";
            for(int j = 0; j < min(p.size(), c.size()); ++j) {
                if(p[j] != c[j]) {
                    if(!adj[p[j]].count(c[j])){
                        ind[c[j]]++;
                        adj[p[j]].insert(c[j]);
                    }
                    break;
                }
            }
        }
        
        queue<char> q;
        for(auto& ref : ind) {
            if(ref.second == 0) q.push(ref.first);
        }
        string ans;
        while(!q.empty()) {
            char c = q.front(); q.pop();
            ans += c;
            for(auto& n : adj[c]) {
                if(--ind[n] == 0) q.push(n);
            }
        }
        
        return ans.size() == ind.size() ? ans : "";
    }
};

2360. Longest Cycle in a Graph


















































class Solution {
    // why topolotical sort?
    // 因為是找出最大的環，所以single linked list可以先砍掉
    // 也就是類似剝洋蔥，先把indegree為0的剃除掉。
public:
    int longestCycle(vector<int>& edges) {
        // calculate indegree of each node
        int sz = edges.size();
        vector<int> in(sz);
        for(int i = 0; i < sz; ++i) {
            if(edges[i] != -1) in[edges[i]]++;
        }
        
        // setup the queue 
        // and push the node which indegree is zero
        queue<int> q;
        vector<int> v(sz);
        for(int i = 0; i < sz; ++i) {
            if(in[i] == 0) {
                v[i] = 1;
                q.push(i);
            }
        }

        // remove the node which indegree is zero
        while(!q.empty()) {
            int x = q.front(); q.pop();
            int& n = edges[x];
            if(n == -1) continue;
            if(--in[n] == 0) {
                q.push(n);
                v[n] = 1;
            }
        }

        // get the result from the rest node
        int ans{-1};
        for(int i = 0; i < sz; ++i) {
            if(v[i]) continue;
            int dist{0};
            for(int j = i; j != -1 && v[j] == 0; j = edges[j]) {
                v[j] = 1;
                dist++;
            }
            ans = max(ans, dist);
        }
        return ans;
    }
};

1857. Largest Color Value in a Directed Graph

  1. 很棒的題目，必做。
  2. 參考官網的解答
  3. why topoligic sort? 因為是有向圖，一層一層走到最後一個node。
  4. 如果indegree不為0，表示還有其他路徑還沒走到這個node，只更新node的state，繼續等待直到indegree為0。
  5. 每個node都maintain一個vector<int>(26)，紀錄到達這個node的color統計。
  6. 判斷是否有cycle，因為topologic sort如果沒cycle會處理過每個node，所以使用processed來計算處理過幾個node，processed不為node個數，表示有cycle。

































class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int sz = colors.size();
        vector<vector<int>> st(sz, vector<int>(26)); // node, count of each color
        vector<int> indegree(sz);
        unordered_map<int, vector<int>> adj; // node, adjust node of this node
        for(auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            indegree[e[1]]++;
        }
        
        queue<int> q; //index of node(which indegree is zero)
        for(int i = 0; i < sz; ++i)
            if(indegree[i] == 0) q.push(i);

        int processed{0}, ans{0};
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            int c = colors[cur] - 'a';
            st[cur][c]++;
            processed++;
            ans = max(ans, st[cur][c]);
            for(auto& next : adj[cur]) {
                for(int i = 0; i < 26; ++i)
                    st[next][i] = max(st[next][i], st[cur][i]);
                if(--indegree[next] == 0) q.push(next);
            }    
        }

        return processed != sz ? -1 : ans;
    }
};

802. Find Eventual Safe States




































class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        // n : no of nodes = graph.size()
        // m : no of edges = sum(graph[i].size());
        unordered_map<int, vector<int>> from; // O(M)
        vector<int> ind(graph.size()); //O(N)
        for(int i = 0; i < graph.size(); ++i) { // O(M)
            ind[i] = graph[i].size();
            for(auto& j : graph[i])
                from[j].push_back(i);
        }
        queue<int> q; //O(N)
        for(int i = 0; i < ind.size(); ++i) {
            if(ind[i] == 0) q.push(i);
        } 
        vector<int> safe(graph.size()); //O(N)
        while(!q.empty()) { // O(N)
            int cur = q.front(); q.pop();
            safe[cur] = 1;
            for(auto& f : from[cur]) {
                if(--ind[f] == 0) q.push(f);
            }
        }
        vector<int> ans; //O(N)
        for(int i = 0; i < safe.size(); ++i)
            if(safe[i])
                ans.push_back(i);
        return ans;
        // time : O(M + N + N + N) = O(M + N)
        // space : O(M + N + N + N) = O(M + N)
    }
};
// terminal node : no outgoing node --> graph[i].size() == 0
// safe node : every possible path starting from this all leads to a terminal node
tags: leetcode 刷題
Select a repo