Introduce

• 必須思考的點
  • node可以多次訪問嗎?

Problems

886. Possible Bipartition

給你一個vector<vector<int>>dislikes, 代表ai不喜歡bi。兩個不喜歡的人不可以在同一個群組，試問可否把他門分成兩個group。

這題和785. Is Graph Bipartite?一樣。

2022/12/21

1. 第一次解這個問題，我是先想到用union-find，因為ai討厭的人全部都成一個群組。
2. 看了官方解答個人覺得使用BFS的塗色方法也很棒。

3. 想法就是，先找出一個沒被塗色的點，將他塗上red。
4. 檢查鄰近點顏色有沒有和上一次塗上的顏色一樣。
5. 接下來把鄰近的點，塗上另一種顏色。
6. 重複3~5步驟

class Solution {
    vector<vector<int>> adj;
    vector<int> color;
    enum type{none = -1, red, blue};
    bool helper(int source) {
        color[source] = red;
        queue<int> q{{source}};
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            for(auto& nxt : adj[cur]) {
                if(color[nxt] == color[cur]) return false;
                if(color[nxt] == none) { 
                    color[nxt] = !color[cur];
                    q.push(nxt);
                }
            }
        }
        return true;
    }
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        int sz = dislikes.size();
        if(sz <= 1) return true;
        adj.resize(n + 1, vector<int>());
        color.resize(n + 1, none);
        for(auto& dis : dislikes) {
            adj[dis[0]].push_back(dis[1]);
            adj[dis[1]].push_back(dis[0]);
        }
        for(int i = 1; i <= n; ++i)
            if(color[i] == none && !helper(i)) return false; 
        return true;
    }
};

207. Course Schedule(Medium)

你必須修numCourses的課程，從[0, numCourses-1]。其中有些必修條件prerequisites[i] = [ai, bi]。當要修ai的時候必須先修bi。試問可否全部課程都修完。

ex: numCourses = 4, prerequisites=[[1, 0],[2, 0],[3, 1],[3, 2]];
因為課程有相依性，所以可以畫成如下的有向圖。

右邊的圖灰色的數字表示，有幾個parent node。也就是需要修過幾門課才可以修此門課。數字0則表示沒相依，可以先修。

使用兩個資料結構來表示課程。
vector<int> needs : 來統計每門課需要預修多少課。
vector<vector<int>> graph : 修完此門課後，可以修那些課。

最後使用queue，來收集目前可以修的課。最後只要看needs有沒有全部為0就可已知道有沒有修完。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> needs(numCourses, 0);
    // 建立needs和graph
    for(auto& req : prerequisites) {
        needs[req[0]]++;
        graph[req[1]].push_back(req[0]);
    }
    // 統計目前可以修的課    
    queue<int> q;
    for(int i = 0; i < numCourses; ++i)
        if(needs[i] == 0) q.push(i);
        
    while(!q.empty()) {
        int t = q.front(); q.pop();
        // 修了t，接著修可以修的課graph[t]
        for(int i = 0; i < graph[t].size(); ++i) {
            needs[graph[t][i]]--;
            //檢查此門課是否可以修了
            if(needs[graph[t][i]] == 0)
                q.push(graph[t][i]);
        }
    }
        
    for(auto& n : needs)
        if(n != 0) return false;
            
    return true;
}

997. Find the Town Judge(Easy)

找出鎮上的法官。給你一個trust的vector，其中trust[i]=[ai, bi]。ai相信bi。
條件: 1. 所有人都相信法官。2. 法官不相信任何人。

1. 此為標準的有向圖。ai->bi。
2. 指向node的數目為此node的入度。指出這個node的數目為此node的出度。
3. 統計每個node的入度和出度。
4. 法官的入度為n-1，出度為0。

int findJudge(int n, vector<vector<int>>& trust) {
    auto m = trust.size();
    if(m == 0) {
        if(n == 1) return 1;
        else return -1;
    }
    vector<int> in(n + 1, 0), out(n + 1, 0);
    int maxcnt{0};
    int maxn;
    for(int i = 0; i < m; ++i) {
        in[trust[i][1]]++;
        out[trust[i][0]]++;
        if(in[trust[i][1]] > maxcnt) {
            maxcnt = in[trust[i][1]];
            maxn = trust[i][1];
        }
    }
        
    if(maxcnt == n - 1 && out[maxn] == 0)
        return maxn;
    else
        return -1;
}

[2101. Detonate the Maximum Bombs

](https://leetcode.com/problems/detonate-the-maximum-bombs/)

• 一開始我用暴力破解，但是到40題答案還是錯
• 官方答案是說，先建立每個bomb可以影響的bomb列表，也就是一個有向的graph。
• 有了這個directed graph就可以針對每個bomb，來看他最多可以到達多少個bombs，使用dfs。
• 我覺得可以背一下使用dfs來計算個數的code snippet。

class Solution {
    unordered_map<int, vector<int>> aff;
    enum st{x, y, r};
    int dfs(int cur, unordered_set<int>& v) {
        v.insert(cur);
        int count = 1; // 目前這個node
        for(auto& n : aff[cur]) {
            if(v.count(n)) continue;
            count += dfs(n, v); // 加上從n出發的sub-graphy的node數 
        }
        return count;
    }
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int sz = bombs.size();
        if(sz == 1) return 1;
        for(int i = 0; i < sz; ++i) {
            for(int j = 0; j < sz; ++j) {
                if(i == j) continue;
                vector<int>& bi = bombs[i];
                vector<int>& bj = bombs[j];
                if(pow(bi[x] - bj[x], 2) + pow(bi[y] - bj[y], 2) <= pow(bi[r], 2))
                    aff[i].push_back(j);
            }
        }
        int ans = 1;
        for(int i = 0; i < sz; ++i) {
            unordered_set<int> v;
            ans = max(ans, dfs(i, v));
        }
        return ans;
    }
};

1514. Path with Maximum Probability

給你一個undirected weighted graph，還有start和end。試找出start->end的最大機率path。

1. 一開始我使用BFS，結果答案有錯。
2. 因為我使用了unordered_set<int> v，來限制訪問過的node。但是第一次訪問機率比較小，第二次訪問機率比較大，這樣還是要繼續給他訪問。

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        unordered_map<int, unordered_map<int, double>> adj;
        for(int i = 0; i < edges.size(); ++i) {
            adj[edges[i][0]].insert({edges[i][1], succProb[i]});
            adj[edges[i][1]].insert({edges[i][0], succProb[i]});
        }
        unordered_set<int> v;
        queue<pair<int, double>> q;
        q.push(make_pair(start, 1.0));
        v.insert(start);
        double ans = 0.0;
        while(!q.empty()) {
            auto [cur, prob] = q.front(); q.pop();
            for(auto& next : adj[cur]) {
                if(next.first == end) {
                    ans = max(ans, prob * next.second);
                } else if(v.count(next.first)) continue;
                else {
                    q.push({next.first, prob * next.second});
                    v.insert(next.first);
                }
            }
        }
        return ans;
    }
};

3. 所以改成紀錄機率的vector。只要到這個點的機率比之前還要大，就會繼續給他訪問。

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        unordered_map<int, unordered_map<int, double>> adj;
        for(int i = 0; i < edges.size(); ++i) {
            vector<int>& e = edges[i];
            double& p = succProb[i];
            adj[e[0]].insert({e[1], p});
            adj[e[1]].insert({e[0], p});
        }
        vector<double> ps(n, 0.0);
        ps[start] = 1.0;
        queue<int> q{{start}};
        double ans = 0.0;
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            for(auto& next : adj[cur]) {
                // 檢查是否機率比之前還大
                if(ps[cur] * next.second > ps[next.first]) {
                    q.push(next.first);
                    ps[next.first] = ps[cur] * next.second;
                }
            }
        }
        return ps[end];
    }
};

4. 上面例子是用queue來從cur檢查每下一個node，即使是機率小的也會檢查。
5. 如果是使用priority_queue從機率大的開始檢查，可以減少很多時間。這樣的做法也稱作"Dijkstra's Algorithm"

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        unordered_map<int, unordered_map<int, double>> adj;
        for(int i = 0; i < edges.size(); ++i) {
            vector<int>& e = edges[i];
            double& p = succProb[i];
            adj[e[0]].insert({e[1], p});
            adj[e[1]].insert({e[0], p});
        }
        vector<double> maxp(n, 0.0);
        maxp[start] = 1.0;
        // 其實不用儲存probability，
        // 但是因為每次都要用priority queue取最大機率，
        // 所以還是儲存起來。
        priority_queue<pair<double, int>> pq;
        pq.push({1.0, start});
        while(!pq.empty()) {
            auto [p, cur] = pq.top(); pq.pop();
            if(cur == end) return p;
            for(auto& next : adj[cur]) {
                if(p * next.second > maxp[next.first]) {
                    maxp[next.first] = p * next.second;
                    pq.push({maxp[next.first], next.first});
                }
            }
        }
        return 0.0;
    }
};

• time complexity =
  $O(m+nlogn)$
  • 其中m為edges大小，建立adj
  • 其中n為最worest case走訪所有的node。
• space complexity =
  $O(m+n)$
  • m : 建立adj的大小
  • n : priority_queue最worest case所有node都必須儲存。