Topological, Tarjan

[sync-by-unito[bot]]

Topological Sort: FB questions: //269. Alien Dictionary //207 Course Schedule //210 Course Schedule II Tarjan's algorithm: Amazon questions: //1192. Critical Connections in a Network Ref: https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ https://www.geeksforgeeks.org/bridge-in-a-graph/ https://www.hackerearth.com/practice/notes/nj/

Topological Sort: //269. Alien Dictionary

class Solution{
public:   
    string alienOrder(vector<string>& words) {
        // Step 0: Initialize adjacent list and the indegree
        unordered_map<char, vector<int>> adj;
        unordered_map<char, int> indegree;
        for(string word : words){
            for(char c : word){
                adj[c] = vector<int>();
                indegree[c] = 0;
            }
        }

        // Step 1: Find all edges, e.g.: w(w-'a')->e, e(e-'a')->r
        for(int i=0; i<words.size()-1; ++i){
            string w1 = words[i];
            string w2 = words[i+1];

            // check if w2 is a prefix of w1, this should bring error.
            if(w1.size() > w2.size() && w1.rfind(w2, 0) == 0)
                return "";

            // initialize the adj list, pick the unique node->node relationship
            for(int j=0; j<min(w1.size(), w2.size()); ++j){
                if(w1[j] != w2[j]){
                    ++indegree[w2[j]];
                    adj[w1[j]].push_back(w2[j]);
                    break;
                }
            }
        }

        // Step 3. All unique characters need to be in topological sort
        queue<char> q; string sorted;
        for(auto v : indegree){
            if(v.second == 0) q.push(v.first);
        }
        while(!q.empty()){
            char cur = q.front(); q.pop(); sorted.push_back(cur);   
            for(auto next : adj[cur]){
                if(--indegree[next] == 0) q.push(next);
            }
        }
        return (sorted.size() == indegree.size())? sorted : "";
    }
};

Tarjan: //1192. Critical Connections in a Network

class Solution {
public:
    vector<vector<int>> adj, bridge;
    vector<int> disc; //discovery time for each node
    vector<int> low; //low-link for each node
    int disc_time = 1;
    stack<int> s;

    void dfs(int v, int parent){
        low[v] = disc[v] = disc_time++;
        s.push(v);

        for( auto &w : adj[v] ){
            if( w == parent ) continue;
            else if( disc[w] == 0 ){ // not visited yet
                dfs(w, v);
                low[v] = min(low[v], low[w]);

                // Find bridges (if v's disc < w's low-link, 
                // means w can't go back to v if connection is broken)
                if(disc[v] < low[w])
                    bridge.push_back( {v, w} );
            }else{
                low[v] = min(low[v], disc[w]);
            }
        }

        if(low[v] == disc[v]){      // [Optional] find root node of a SCC,
            while(v != s.top()){    //print SCC nodes
                cout << s.top() << ",";
                s.pop();
            }
            cout << s.top() << endl;//print root node of a SCC
            s.pop();
        }
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        // Step 1. Initialize adjacent list by turning connections to directed edges
        adj.resize(n);
        disc.resize(n);
        low.resize(n);
        for(vector<int> &c : connections){
            adj[c[0]].push_back(c[1]);
            adj[c[1]].push_back(c[0]);
        }

        // Step 2. Use tarjan's algorithm to find SCCs and bridges
        for(int i=0; i < n; i++){
            if(disc[i] == 0) // if discovery time is 0, means it's not visited yet.
                dfs(i, -1);
        }

        // Step 3. Return bridges (critical connections)
        return bridge;
    }
};

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//269. Alien Dictionary [Hard] //BFS

class Solution{ public:
string alienOrder(vector& words) { // Step 0: Initialize adjacent list and the indegree unordered_map<char, vector> adj; unordered_map<char, int> indegree; for(string word : words){ for(char c : word){ adj[c] = vector(); indegree[c] = 0; } }

    // Step 1: Find all edges, e.g.: w(w-'a')->e, e(e-'a')->r
    for(int i=0; i<words.size()-1; ++i){
        string w1 = words[i];
        string w2 = words[i+1];

        // check if w2 is a prefix of w1, this should bring error.
        if(w1.size() > w2.size() && w1.rfind(w2, 0) == 0)
            return "";

        // initialize the adj list, pick the unique node->node relationship
        for(int j=0; j<min(w1.size(), w2.size()); ++j){
            if(w1[j] != w2[j]){
                ++indegree[w2[j]];
                adj[w1[j]].push_back(w2[j]);
                break;
            }
        }
    }

    // Step 3. All unique characters need to be in topological sort
    queue<char> q; string sorted;
    for(auto v : indegree){
        if(v.second == 0) q.push(v.first);
    }
    while(!q.empty()){
        char cur = q.front(); q.pop(); sorted.push_back(cur);   
        for(auto next : adj[cur]){
            if(--indegree[next] == 0) q.push(next);
        }
    }
    return (sorted.size() == indegree.size())? sorted : "";
}

};//DFS

class Solution_q269 { public: unordered_map<char, list*> adj; unordered_map<char, int> visited; string sorted;

void topologicalSortUtil(char c) {
    // Mark the current node as visited. 
    visited[c] = 1; //1: visiting

    // Recur for all the vertices adjacent to this vertex 
    for (auto it = adj[c]->cbegin(); it != adj[c]->cend(); ++it) {
        if (visited[*it] == 1) return; //visiting itself, cyclic
        if (visited[*it] == 0)
            topologicalSortUtil((*it));
    }

    // Push current vertex to stack which stores result 
    visited[c] = 2;
    sorted.push_back(c);
    return;
}

string alienOrder(vector<string>& words) {
    // Step 0: Put all unique letters into adj as keys.
    for (string word : words) {
        for (char c : word) {
            if (!visited.count(c)) {
                adj[c] = new list<char>;
                visited[c] = 0;
            }
        }
    }

    // Step 1: Find all edges, e.g.: w(w-'a')->e, e(e-'a')->r
    for (int i = 0; i < words.size() - 1; ++i) {
        string word1 = words[i];
        string word2 = words[i + 1];

        // Check that word2 is not word1's prefix, e.g.: 1: "abcd", 2: "ab"
        if (word1.size() > word2.size() && word1.rfind(word2, 0) == 0)
            return "";

        // Find the first non-match, insert the relationship into adjacent list
        for (int j = 0; j < min(word1.size(), word2.size()); ++j) {
            if (word1[j] != word2[j]) {
                adj[word1[j]]->push_back(word2[j]);
                break;
            }
        }
    }

    // Step3. All unique characters need to be in topological sort
    for (auto kv : visited) {
        if (visited[kv.first] == 0)
            topologicalSortUtil(kv.first);
    }

    cout << sorted.size() << ", " << adj.size() << ", " << visited.size();
    reverse(sorted.begin(), sorted.end());
    return (sorted.size() == visited.size()) ? sorted : "";
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//207 Course Schedule [Med] //BFS

class Solution { public: bool canFinish(int n, vector<vector>& prerequisites) { // step0. initialize adjacent list, and indegree for doing bfs vector<vector> adj (n, vector()); vector indegree (n, 0);

    // step1. fill adj lists
    for(vector<int> &r : prerequisites){
        adj[r[1]].push_back(r[0]);
        indegree[r[0]]++;
    }

    // step2. take all the unique keys to do topological sort, start from indegree 0
    queue<int> q;
    for(int i=0; i<n; ++i){
        if(indegree[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int cur = q.front(); q.pop(); --n;
        for(auto next: adj[cur]){
            if(--indegree[next] == 0) q.push(next);
        }
    }

    return n == 0;
}

};//DFS

class Solution { public: unordered_map<int, list*> adj; unordered_map<int, int> visited;

// step3. during the topological sort, we check if there is any cylic condition.
bool topologicalSort(int i) {
    visited[i] = 1; // 1: visisting
    for (auto it = adj[i]->cbegin(); it != adj[i]->cend(); ++it) {
        if (visited[*it] == 1)
            return false; //cylic condition, dead lock
        if (visited[*it] == 0)
            if (!topologicalSort(*it))
                return false;
    }
    visited[i] = 2;
    return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // step0. initialize adjacent list, and visited map for doing dfs
    for(int i=0; i<numCourses; ++i){
        visited[i] == 0;
        adj[i] = new list<int>;
    }
    // step1. fill adj lists
    for(vector<int>& r :  prerequisites){
        adj[r[1]]->push_back(r[0]);
    }

    // step2. take all the unique keys to do topological sort
    for(auto kv : visited){
        if(visited[kv.first] == 0){
            if(!topologicalSort(kv.first)) return false;
        }
    }
    return true;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//210. Course Schedule II //BFS

class Solution { public: vector findOrder(int n, vector<vector>& prerequisites) { // step0. initialize adjacent list, and indegree for doing bfs topological sort vector<vector> adj (n, vector()); vector indegree (n, 0);

    // step1. fill adj lists, r[1]: key, r[0]: to vertex node
    for(vector<int>& r : prerequisites){
        adj[r[1]].push_back(r[0]);
        ++indegree[r[0]];
    }

    // step2. for every unique keys, do topological sort.
    queue<int> q; vector<int> sorted;
    for(int i=0; i<n; ++i){
        if(indegree[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int cur = q.front(); q.pop(); --n; sorted.push_back(cur);
        for(int next : adj[cur]){
            if( --indegree[next] == 0) q.push(next);
        }
    }
    if(n != 0) return {};
    return sorted;
}

};//DFS

class Solution { public: vector findOrder(int n, vector<vector>& prerequisites) { // step0. initialize adjacent list, and indegree for doing bfs topological sort vector<vector> adj (n, vector()); vector indegree (n, 0);

    // step1. fill adj lists, r[1]: key, r[0]: to vertex node
    for(vector<int>& r : prerequisites){
        adj[r[1]].push_back(r[0]);
        ++indegree[r[0]];
    }

    // step2. for every unique keys, do topological sort.
    queue<int> q; vector<int> sorted;
    for(int i=0; i<n; ++i){
        if(indegree[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int cur = q.front(); q.pop(); --n; sorted.push_back(cur);
        for(int next : adj[cur]){
            if( --indegree[next] == 0) q.push(next);
        }
    }
    if(n != 0) return {};
    return sorted;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//329 Longest Increasing Path in a Matrix [Hard] //BFS

class Solution { public: int longestIncreasingPath(vector<vector>& matrix) { if(matrix.empty()) return 0; // Step 0. Initialize adjacent list and indegree. int rows = matrix.size(), cols = matrix[0].size(); vector<vector> indegree (rows, vector(cols, 0));

    // Step 1. Build our adjacent list (not really adj list in this case, 
    // because when we do topological sort later, 
    // we'll use indegree and 4 direction which way we can go (like an adjacent list)), 
    // 4-direction and only from small to big.
    vector<vector<int>> dirs = { {0,1}, {0,-1}, {1,0}, {-1,0} };
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < cols; ++y) {
            for (auto& dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                    matrix[nx][ny] > matrix[x][y])
                        indegree[nx][ny]++;
            }
        }
    }

    // Step 2. For each of number, start from indegree == 0 and do topological sort.
    queue<pair<int, int>> q;
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < cols; ++y) {
            if (indegree[x][y] == 0) q.push({ x, y });
        }
    }

    // Step 3. BFS and find the length.
    int len = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size-- > 0) { // KEY:consume all nodes in cur layer and add next layer into queue
            auto cur = q.front(); q.pop();
            for (auto& dir : dirs) {
                int nx = cur.first + dir[0];
                int ny = cur.second + dir[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols &&
                    matrix[nx][ny] > matrix[cur.first][cur.second]) {
                    if (--indegree[nx][ny] == 0)
                        q.push({ nx, ny });
                }
            }
        }
        ++len;
    }
    return len;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//1192. Critical Connections in a Network

class Solution { public: vector<vector> adj, bridge; vector disc; //discovery time for each node vector low; //low-link for each node int disc_time = 1; stack s;

void dfs(int v, int parent){
    low[v] = disc[v] = disc_time++;
    s.push(v);

    for( auto &w : adj[v] ){
        if( w == parent ) continue;
        else if( disc[w] == 0 ){ // not visited yet
            dfs(w, v);
            low[v] = min(low[v], low[w]);

            // Find bridges (if v's disc < w's low-link, 
            // means w can't go back to v if connection is broken)
            if(disc[v] < low[w])
                bridge.push_back( {v, w} );
        }else{
            low[v] = min(low[v], disc[w]);
        }
    }

    if(low[v] == disc[v]){      // [Optional] find root node of a SCC,
        while(v != s.top()){    //print SCC nodes
            cout << s.top() << ",";
            s.pop();
        }
        cout << s.top() << endl;//print root node of a SCC
        s.pop();
    }
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    // Step 1. Initialize adjacent list by turning connections to directed edges
    adj.resize(n);
    disc.resize(n);
    low.resize(n);
    for(vector<int> &c : connections){
        adj[c[0]].push_back(c[1]);
        adj[c[1]].push_back(c[0]);
    }

    // Step 2. Use tarjan's algorithm to find SCCs and bridges
    for(int i=0; i < n; i++){
        if(disc[i] == 0) // if discovery time is 0, means it's not visited yet.
            dfs(i, -1);
    }

    // Step 3. Return bridges (critical connections)
    return bridge;
}

};