class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> type = vector<int>(graph.size(), 0); 
        
        queue<int> q;
        
        for(int i = 0;i < graph.size();i++) {        
            if(type[i] == 0) {
                // 只要是沒看過的節點，一律設為 type 1
                q.push(i);
                type[i] = 1;
            } else {
                continue;
            }            // BFS
            while(!q.empty()) {
                int nown = q.front();
                q.pop();                // 所有的邊都遍尋一遍，看有沒有不合規則的
                for(int j = 0;j < graph[nown].size();j++) {
                    if(type[graph[nown][j]] == type[nown]) {
                        // 跟節點同一 type ==> 不符規則
                        return false;
                    } else if(type[graph[nown][j]] == 0) {
                        // 假如是還沒選定 type 的節點
                        // 填上與 nown 節點不同的 type
                        q.push(graph[nown][j]);
                        if(type[nown] == 1) {
                            type[graph[nown][j]] = 2;
                        } else {
                            type[graph[nown][j]] = 1;
                        }
                    } else {
                        // 已經選定 type，且符合規則
                        // 不須遍尋，直接跳過
                    }
                }
            }
        }
        return true;
    }
};

LeetCode : 207. Course Schedule

使用 topological sort 來偵測環

TODO ：嘗試其他偵測環的方式

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<int> inDegree = vector<int>(numCourses, 0);
        unordered_map<int, vector<int>> g;
        
        for(int i = 0;i < prerequisites.size();i++) {
            inDegree[prerequisites[i][0]]++;
            g[prerequisites[i][1]].push_back(prerequisites[i][0]); 
        } 
        
        queue<int> q;
        int numOfToPoSort = 0;
        
        for(int i = 0;i < inDegree.size();i++) {
            if(0 == inDegree[i]) {
                q.push(i);
            }
        }
        
        while(!q.empty()) {
            int nown = q.front();
            numOfToPoSort++;
            q.pop();
            
            vector<int> &v = g[nown];
            for(int i = 0;i < v.size();i++) {
                inDegree[v[i]]--;
                if(0 == inDegree[v[i]]) {
                    q.push(v[i]);
                }
            }
        }        return numCourses == numOfToPoSort;
    }
};

LeetCode : 210. Course Schedule II

正宗 topological sort 題目

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> inDegree = vector<int>(numCourses, 0);
        unordered_map<int, vector<int>> g;
        for(int i = 0;i < prerequisites.size();i++) {
            inDegree[prerequisites[i][0]]++;
            g[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        
        queue<int> q;
        
        for(int i = 0;i < numCourses;i++) {
            if(0 == inDegree[i]) {
                q.push(i);
            }
        }
        
        vector<int> toPoSort;
        
        while(!q.empty()) {
            int nown = q.front();
            toPoSort.push_back(nown);
            q.pop();
            
            vector<int> &v = g[nown];
            for(int i = 0;i < v.size();i++) {
                inDegree[v[i]]--;
                if(0 == inDegree[v[i]]) {
                    q.push(v[i]);
                }
            }
        }
        
        return toPoSort.size() == numCourses ? toPoSort : vector<int>(0);
    }
};

LeetCode : 269. Alien Dictionary

TODO：看一下其他人是怎麼做的

/*
[a,b,c]
[a,b] 
--> 這類排序錯誤直接可斷定為 ""
*/class Solution {
public:
    string alienOrder(vector<string>& words) {
        string s;
        
        int numWord = 0;
        unordered_map<char, vector<char>> g;
        unordered_map<char, unordered_map<char, bool>> visited;
        vector<int> inDegree = vector<int>(26, 0);
        vector<bool> exist  = vector<bool>(26, false);        
        
        for(int i = 0;i < words.size();i++) {
            for(int j = 0;j < words[i].size();j++) {
                if(!exist[words[i][j] - 'a']) {
                    exist[words[i][j] - 'a'] = true;
                    numWord++;
                }
            }
            for(int j = i + 1;j < words.size();j++) {
                int len = min(words[i].size(), words[j].size());
                int index;
                
                // check the input is correct 
                // ( lexicographically )
                for(index = 0;index < len;index++) {
                    if(words[i][index] != words[j][index]) {
                        break;
                    }
                }                
                // the input is not correct!
                if(index == words[j].size() && index != words[i].size()) {
                    return "";
                }
                
                
                for(int q = 0;q < len;q++) {
                    if(words[i][q] != words[j][q]) {
                        // 使用 visited 來避免加入相同的邊
                        if(!visited[words[i][q]][words[j][q]]) {
                            visited[words[i][q]][words[j][q]] = true;                   
                            inDegree[words[j][q] - 'a']++;
                            g[words[i][q]].push_back(words[j][q]);
                        }
                        break;
                    }
                }
            }
        }
        
        queue<char> q;
        for(char i = 0;i < 26;i++) {
            if(0 == inDegree[i] && exist[i]) {
                q.push(i + 'a');
            }
        }
        
        // topological sort
        while(!q.empty()) {
            char nowc = q.front();
            s += nowc;
            q.pop();
            
            vector<char> &v = g[nowc];
            
            for(int i = 0;i < v.size();i++) {
                inDegree[v[i] - 'a']--;
                if(0 == inDegree[v[i] - 'a']) {
                    q.push(v[i]);
                }
            }
        }        return s.size() == numWord ? s : "";
    }
};

LeetCode : 778. Swim in Rising Water

使用 priority queue 去記錄海拔最小的節點，並從海拔較小的節點開始進行 BFS。

class Solution {
private:
    int t = 0;
    int X[4] = {0, 0, 1, -1};
    int Y[4] = {1, -1, 0, 0};
public:
    int swimInWater(vector<vector<int>>& grid) {
        vector<vector<bool>> visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        
        pq.push({grid[0][0], 0, 0});
        visited[0][0] = true;
        
        while(!pq.empty()) {
            vector<int> nown = pq.top();
            pq.pop();
            
            int e = nown[0];
            int x = nown[1];
            int y = nown[2];
            
            if(x == grid.size() - 1 &&
               y == grid[0].size() - 1) {
                return max(e, t);
            }
            
            if(e > t) {
                t = e;
            }
            
            for(int i = 0;i < 4;i++) {
                int newx = x + X[i];
                int newy = y + Y[i];
                
                if(newx >= 0 && newx < grid.size() &&
                   newy >= 0 && newy < grid[0].size() && !visited[newx][newy]) {
                    visited[newx][newy] = true;
                    pq.push({grid[newx][newy], newx, newy});
                }
            }
        }
        
        return 0;
    }
};

LeetCode : 1820. Maximum Number of Accepted Invitations

稀有的 bipartite matching 題目。
TODO : 用 Flow 的概念作這一題。

// maximum bipartite matching
// Reference
// https://web.ntnu.edu.tw/~algo/Matching.html#4/*
Cardinality ( 基數 )
一個匹配擁有的匹配邊數目Alternating Path ( 交錯路徑 )
Alternating Cycle ( 交錯環 )
在一張存在匹配的圖上，匹配邊和未匹配邊彼此相間的一條路徑與一個環Augmenting Path ( 擴充路徑 )
一條交錯路徑，第一個點和最後一個點都是未匹配點。因此第一條邊和最後一條邊都是未匹配邊
擴充路徑有個更有趣的特性：顛倒擴充路徑上的匹配邊和未匹配邊，可以改變匹配，並且讓 Cardinality 加一https://web.ntnu.edu.tw/~algo/Matching.html#4*/class Solution {
private:
    vector<int> bm; // boys  match
    vector<int> gm; // girls match
    
    vector<vector<int>> bg; // boys graph
    vector<vector<int>> gg; // girls graph
    
    bool dfs(int b, vector<vector<int>> &grid, vector<bool> &visited) {
        
        for(int i = 0;i < bg[b].size();i++) {
            int girl = bg[b][i];
            if(!visited[girl]) {
                visited[girl] = true;
                if(-1 == gm[girl] || dfs(gm[girl], grid, visited)) {
                    bm[b] = girl;
                    gm[girl] = b;
                    return true;
                }
            }
        }
        
        return false;
    }
    
public:
    int maximumInvitations(vector<vector<int>>& grid) {
        vector<bool> visited;
        
        bm = vector<int>(grid.size(), -1);
        gm = vector<int>(grid[0].size(), -1);
        
        bg = vector<vector<int>>(grid.size());
        gg = vector<vector<int>>(grid[0].size());
        
        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                if(1 == grid[i][j]) {
                    bg[i].push_back(j);
                    gg[j].push_back(i);
                }
            }
        }
        
        int num = 0;
        for(int i = 0;i < bg.size();i++) {
            visited = vector<bool>(gg.size(), false);
            if(dfs(i, grid, visited)) {
                // 每找到一個 Augmenting Path ， Cardinality 加 1
                num++;
            }
        }
        
        return num;
    }
};

LeetCode : 2115. Find All Possible Recipes from Given Supplies

注意有可能會出現環。

TODO : 效能太差。

class Solution {
private:
    
    bool dfs(string &s, vector<vector<string>>& ingredients, unordered_map<string, bool> &s2b, unordered_map<string, int> &s2i, unordered_map<string, bool> &s2v) {        
        if(s2b.find(s) != s2b.end()) {
            return true;
        }
        
        if(s2i.find(s) == s2i.end()) {
            return false;
        }
        
        if(s2v[s]) {
            return false;
        }
        s2v[s] = true;
        
        int index = s2i[s];
        
        
        for(int i = 0;i < ingredients[index].size();i++) {
            if(s2b.find(ingredients[index][i]) == s2b.end()) {
                if(!dfs(ingredients[index][i], ingredients, s2b, s2i, s2v)) {
                    return false;   
                }
            }
        }
        
        s2v[s] = false;
        return true;
    }
    
public:
    
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        vector<string> ans;
        unordered_map<string, bool> s2b;
        unordered_map<string, int> s2i;
        unordered_map<string, bool> s2v;
        
        for(int i = 0;i < supplies.size();i++) {
            s2b[supplies[i]] = true;
        }
        
        for(int i = 0;i < recipes.size();i++) {
            s2i[recipes[i]] = i;
        }
    
        for(int i = 0;i < recipes.size();i++) {
            if(dfs(recipes[i], ingredients, s2b, s2i, s2v)) {
                ans.push_back(recipes[i]);
            }
        }
        
        return ans;
    }
};

LeetCode 1059. All Paths from Source Lead to Destination

TODO : 太慢，想些辦法加速

class Solution {
public:
    
    bool dfs(int index, unordered_map<int, vector<int>> &g, unordered_map<int, int> &state) {
        
        vector<int> &edges = g[index];
        for(int i = 0;i < edges.size();i++) {
            if(0 == state[edges[i]]) {
                state[edges[i]] = 1;
                bool res = dfs(edges[i], g, state);
                if(!res) {
                    return false;
                }
                state[edges[i]] = 2;
            } else if(1 == state[edges[i]]) {
                return false;
            } else if(2 == state[edges[i]]) {
                
            }
        }
        
        return true;
    }
    
    bool dfs2(int index, unordered_map<int, vector<int>> &g, unordered_map<int, int> &state, int dest) {
        if(index == dest) {
            return true;
        }
        
        // 最後的點不是 dest
        if(0 == g[index].size()) {
            return false;
        }
        
        vector<int> &edges = g[index];
        for(int i = 0;i < edges.size();i++) {
            if(0 == state[edges[i]]) {
                state[edges[i]] = 1;
                bool res = dfs2(edges[i], g, state, dest);
                if(!res) {
                    return false;
                }
                state[edges[i]] = 2;
            } else if(1 == state[edges[i]]) {
                return false;  
            } else if(2 == state[edges[i]]) {
                
            }
        }
        
        return true;
    }
    
    
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        
        unordered_map<int, vector<int>> g;
        for(int i = 0;i < edges.size();i++) {
            g[edges[i][0]].push_back(edges[i][1]);
        } 
        
        // destination 不能有 outgoing edge
        if(0 != g[destination].size()) {
            return false;
        }
        
        // 不能有環
        // --> 不該檢查所有的環，只需檢查從 source 開始有無環
        // 0 : not visit
        // 1 : visiting
        // 2 : visited
        unordered_map<int, int> state;
        /*for(int i = 0;i < n;i++) {
            bool res = dfs(i, g, state);
            if(!res) {
                return false;
            }
        }*/
        
        // 從 source 到 dest
        state.clear();
        return dfs2(source, g, state, destination);
    }
};

LeetCode : 2285. Maximum Total Importance of Roads

out degree 越多的節點，就該有越高的權重

#define LL long long
class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        
        vector<int> outd = vector<int>(n, 0);
        for(int i = 0;i < roads.size();i++) {
            outd[roads[i][0]]++;
            outd[roads[i][1]]++;
        }
        
        LL ans = 0;
        sort(outd.begin(), outd.end());
        
        LL nowv = n;
        for(int i = outd.size() - 1;i >= 0;i--) {
            ans += nowv * outd[i];
            nowv--;
        }
        
        return ans;
    }
};

LeetCode : 1034. Coloring A Border

class Solution {
public:
    
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1}; 
    
    void dfs(int x, int y, vector<vector<int>> &ans, vector<vector<bool>> &visited, vector<vector<int>>& grid, int ori, int color) {
        
        bool f = false;
        for(int i = 0;i < 4;i++) {
            int newx = x + X[i];
            int newy = y + Y[i];
            
            
            
            if(newx >= 0 && newx < grid.size() &&
               newy >= 0 && newy < grid[0].size()) {
                
                if(grid[newx][newy] != ori) {
                    f = true;
                }
                
                if(!visited[newx][newy]) {
                    visited[newx][newy] = true;
                    
                    if(grid[newx][newy] == ori) {
                        dfs(newx, newy, ans, visited, grid, ori, color);   
                    }
                }
            } else {
                f = true;
            }
        }
        
        if(f) {
            ans[x][y] = color;
        }
    } 
    
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        vector<vector<int>> ans = grid;
        vector<vector<bool>> visited = vector<vector<bool>> (grid.size(), vector<bool>(grid[0].size(), false));        
        if(ans[row][col] == color) {
            return ans;
        }
        
        visited[row][col] = true;
        dfs(row, col, ans, visited, grid, grid[row][col], color);
        
        return ans;
    }
};

LeetCode : 802. Find Eventual Safe States

class Solution {
public:
    
    void dfs(int nown, vector<vector<int>>& g, vector<int> &s, vector<int> &t) {
        
        vector<int> &e = g[nown];
        
        for(int i = 0;i < e.size();i++) {
            if(1 == s[e[i]]) {
                t[nown] = 1;
            } else if(2 == s[e[i]]) {
                
                // 碰到 un-safe 的點，
                // 自己也會變成 un-safe
                if(1 == t[e[i]]) {
                    t[nown] = 1;
                }
                
            } else if(0 == s[e[i]]) {
                // 標示為 visiting
                s[e[i]] = 1;
                dfs(e[i], g, s, t);
                
                // 碰到 un-safe 的點，
                // 自己也會變成 un-safe
                if(1 == t[e[i]]) {
                    t[nown] = 1;
                }
                
            }
        }
        
        // 假如都沒撞到
        if(0 == t[nown]) {
            t[nown] = 2;   
        }
        
        // 標示為 visited
        s[nown] = 2;
    }
    
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> ans;
        // unordered_map<int, int>
        
        // status : 0 : not visited
        // status : 1 : visiting
        // status : 2 : visited
        vector<int> status = vector<int>(graph.size(), 0);
        
        // type : 0 : unknown
        // type : 1 : not safe
        // type : 2 : safe
        vector<int> type = vector<int>(graph.size(), 0);
        
        for(int i = 0;i < graph.size();i++) {
            if(0 == status[i]) {
                dfs(i, graph, status, type);
            }
        }
        
        for(int i = 0;i < type.size();i++) {
            if(2 == type[i]) {
                ans.push_back(i);
            }
        }
        
        sort(ans.begin(), ans.end());
        
        return ans;
    }
};

LeetCode : 886. Possible Bipartition

// TODO : 試試 Union-Find
class Solution {
public:
    
    bool dfs(int nowi, vector<vector<int>> &g, unordered_map<int, bool> &g1, unordered_map<int, bool> &g2, vector<bool> &visited) {
        
        vector<int> &e = g[nowi];
        
        int group = 0;
        if(g1.find(nowi) != g1.end()) {
            group = 1;
        } else {
            group = 2;
        }
        
        for(int i = 0;i < e.size();i++) {
            if(!visited[e[i]]) {
                visited[e[i]] = true;
                if (1 == group) {
                    g2[e[i]] = true;
                } else if (2 == group) {
                    g1[e[i]] = true;
                }
                dfs(e[i], g, g1, g2, visited);
            } else {
                if (1 == group && g1.find(e[i]) != g1.end()) {
                    return false;
                } else if (2 == group && g2.find(e[i]) != g2.end()) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        
        vector<vector<int>> g = vector<vector<int>>(n + 1);
        
        // group1
        unordered_map<int, bool> g1;
        // group2
        unordered_map<int, bool> g2;
        
        vector<bool> visited = vector<bool>(n + 1, false);
        
        for(int i = 0;i < dislikes.size();i++) {
            g[dislikes[i][0]].push_back(dislikes[i][1]);
            g[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        
        
        for(int i = 1;i < g.size();i++) {
            if(!visited[i]) {
                g1[i] = true;
                visited[i] = true;
                if(!dfs(i, g, g1, g2, visited)) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

LeetCode : 2374. Node With Highest Edge Score

#define LL long long
class Solution {
public:
    int edgeScore(vector<int>& edges) {
        
        vector<LL> v = vector<LL>(edges.size(), 0);
        
        for(int i = 0;i < edges.size();i++) {
            v[edges[i]] += i;
        }
        
        LL maxVal = 0;
        int ans = -1;
        for(int i = 0;i < v.size();i++) {
            if(v[i] > maxVal) {
                maxVal = v[i];
                ans = i;
            }
        }
        
        return ans;
    }
};

LeetCode : 261. Graph Valid Tree

// medium or hard ?
// 檢測圖中有無環
// DFS ?
class Solution {
public:
    
    // visited num
    int vn = 0;
    bool dfs(int nowi, int parent, unordered_map<int, vector<int>> &g, vector<bool> &visited) {
        vector<int> &e = g[nowi];
        for(int i = 0;i < e.size();i++) {
            if(e[i] != parent) {
                if(visited[e[i]]) {
                    return false;
                }
                vn++;
                visited[e[i]] = true;
                if(!dfs(e[i], nowi, g, visited)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool validTree(int n, vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> g;
        vector<bool> visited = vector<bool>(n, false);
        
        for(int i = 0;i < edges.size();i++) {
            g[edges[i][0]].push_back(edges[i][1]);
            g[edges[i][1]].push_back(edges[i][0]);
        }
        
        vn++;
        visited[0] = true;
        bool result = dfs(0, -1, g, visited);
        if(!result) {
            return false;
        }
        
        return vn == n ? true : false;
    }
};

LeetCode : 1730. Shortest Path to Get Food

// 應該是... easy 吧
// BFStypedef struct Node Node;
struct Node {
    int x;
    int y;
    int dis;
};class Solution {
public:
    
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    
    int getFood(vector<vector<char>>& grid) {
        vector<vector<bool>> visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size()));
        
        int x, y;
        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                if('*' == grid[i][j]) {
                    x = i;
                    y = j;
                }
            }
        }
        
        queue<Node> q;
        q.push({x, y, 0});
        while(!q.empty()) {
            Node nown = q.front();
            q.pop();
            
            int nowx = nown.x;
            int nowy = nown.y;
            int nowd = nown.dis;
            
            for(int i = 0;i < 4;i++) {
                int newx = nowx + X[i];
                int newy = nowy + Y[i];
                int newd = nowd + 1;
                
                if (newx >= 0 && newx < grid.size() &&
                    newy >= 0 && newy < grid[0].size() &&
                    !visited[newx][newy] &&
                    'X' != grid[newx][newy]) {
                    
                    if('#' == grid[newx][newy]) {
                        return newd;
                    }
                    
                    visited[newx][newy] = true;
                    q.push({newx, newy, newd});
                }
            }
        }
        
        return -1;
    }
};

LeetCode : 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

// TODO : 效能太差了

bool edge_sort(vector<int> &a, vector<int> &b) {
    return a[2] < b[2];
}
class Solution {
private:
    int disjoint_set_find(int x, vector<int> &p) {
        if (p[x] == x) {
            return x;
        }
        p[x] = disjoint_set_find(p[x], p);
        return p[x];
    }

    void disjoint_set_union(int x, int y, vector<int> &p) {
        x = disjoint_set_find(x, p);
        y = disjoint_set_find(y, p);
        p[x] = y;
        return;
    }

    // function : 
    // --> 0 : normal mst
    // --> 1 : delete an edge
    // --> 2 : add an edge into list in the beginning
    // e : 
    // --> the edge that will be delete or add into list
    int mst(int n, vector<vector<int>> &edges, int function, vector<int> &e) {
        vector<int> p = vector<int>(n);
        int sum = 0;
        for(int i = 0;i < n;i++) {
            p[i] = i;
        }

        if(function == 2) {
            sum += e[2];
            disjoint_set_union(e[0], e[1], p);
        }

        for (int i = 0;i < edges.size();i++) {
            if ((function == 1 || function == 2) && 
                edges[i] == e) {
                continue;
            }
            int x = disjoint_set_find(edges[i][0], p);
            int y = disjoint_set_find(edges[i][1], p);
            if(x != y) {
                sum += edges[i][2];
                disjoint_set_union(x, y, p);
            }
        }

        return sum;
    }
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        vector<vector<int>> ans = vector<vector<int>>(2);
        vector<bool> critical = vector<bool>(edges.size(), false);

        for(int i = 0;i < edges.size();i++) {
            edges[i].push_back(i);
        }
        sort(edges.begin(), edges.end(), edge_sort);

        // 1. 跑一次 MST ， 取得 MST 的 total weight
        int sum = mst(n, edges, 0, edges[0]);

        // 2. 遍尋每個邊，尋找 critical edges
        for(int i = 0;i < edges.size();i++) {
            int localsum = mst(n, edges, 1, edges[i]);
            if(localsum != sum) {
                critical[i] = true;
                ans[0].push_back(edges[i][3]);
            }
        }

        // 3. 遍尋除了 critical edges 以外的每個邊，尋找 Pseudo-Critical Edges
        for(int i = 0;i < edges.size();i++) {
            if(critical[i]) {
                continue;
            }
            int localsum = mst(n, edges, 2, edges[i]);
            if(localsum == sum) {
                ans[1].push_back(edges[i][3]);
            }
        }

        return ans;
    }
};

Reference

topological sort — 演算法筆記

Algorithms & Data Structures : Graph : Problems

Problems

LeetCode : 785. Is Graph Bipartite?