lcGraph2 - 图的常见题集2

Posted on 2022-06-25 Edited on 2023-08-03

0 图常见算法

并查集就不提了，算连通性的

dijstra，单元点最短路径

tarjan算法：

trajan 塔杨算法求割点(关键点)，割边

1192criticalConnections 查找集群内的「关键连接」

1 题目

https://leetcode.cn/problems/critical-connections-in-a-network/

2 解题思路

1 解题思路：使用tarjan算法：求割点和割边
- 算法实现参考：https://www.cnblogs.com/collectionne/p/6847240.html
- 一句话概括算法：dfsNo[i]: i号节点dfs的顺序， low[i]：i号节点以及其子树中所有的搜索节点仅通过回边能够到达的节点的dfs序号(回边：非搜索树上的边)，若对于边u->v,有：dfsNo[u] < low[v]，说明v通过回边无法到达u之前的节点，那么说明uv为割边，必须是小于，因为若果回边能回到u，且dfsNo[u] == low[v]，则说明uv不是割边！
- 同理，dfsNo[u] <= low[v]可以得出u为割点，之所以有等于号，是因为u是可以被割的

class Solution {
public:
    
    void Tarjan(vector<vector<int>>& g, int st, vector<int>& parent, vector<int>& low, vector<int>& dfsNo, int no, set<int>& cutPoints, vector<vector<int>>& cutEdges) {
        int rootChildNum = 0;
        low[st] = dfsNo[st] = no;
        for(auto neighbor : g[st]) {
            // if(parent[neighbor] == st) {
            //     continue;
            // }
            if(-1 != dfsNo[neighbor]) { // st -> neighbor 是一条回边
                if(parent[st] != neighbor) { // 且不在搜索子树内
                    low[st] = min(low[st], dfsNo[neighbor]); // 更新low[st]为所有能通过回边到达的最小的dfsNo
                }
            } else {
                parent[neighbor] = st;
                ++rootChildNum;
                
                ++no;
                // cout << "u/v " << st<<"/"<<neighbor << " " << no << endl;
                Tarjan(g, neighbor, parent, low, dfsNo, no, cutPoints, cutEdges);
                low[st] = min(low[st], low[neighbor]); // 更新为所有搜索子树节点中能够通过回边到达的最小的dfsNo
                
                if(-1 != parent[st] && dfsNo[st] <= low[neighbor]) {
                    cutPoints.insert(st);
                }
                if(dfsNo[st] < low[neighbor]) {
                    cutEdges.emplace_back(vector<int>{st, neighbor});
                }
            }
        }
        if(parent[st] == -1 && rootChildNum >= 2) {
            cutPoints.insert(st);
        }
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        // build graph
        vector<vector<int>> g(n);
        for(auto e : connections) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }

        vector<int> dfsNo(n, -1);
        vector<int> low(n, -1); // low[i]：i号节点以及其子树中所有的搜索节点仅通过 回边 能够到达的节点的dfs序号(回边：非搜索树上的边)
        vector<int> parent(n, -1); // 记录搜索树
        int no = 0;

        set<int> cutPoints;
        vector<vector<int>> cutEdges;
        dfsNo[0] = 0;
        Tarjan(g, 0, parent, low, dfsNo, no, cutPoints, cutEdges);
        for(auto i : cutPoints) {
            cout << i << " ";
        }
        cout << "low: ";
        for(auto i : low) {
            cout << i << " ";
        }
        cout << "\ndfsNo: ";
        for(auto no : dfsNo) {
            cout << no << " ";
        }
        return cutEdges;
    }
};

tarjan求连通子集

https://byvoid.com/zhs/blog/scc-tarjan/
当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

1 题集

0882reachableSubNodes 细分图中的可到达结点 dijstra

1 题目

https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/

2 解题思路

1 解题思路：类似的题目：https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference/
- 1.1 dijstra算出来到所有顶点的距离
- 1.2 最终能到达的节点由两部分构成：
  - a : 来自原始节点，要求距离小于maxMoves
  - b : 来自细分节点：很简单，对于每个边uv，从u和v出发，分别还能前进maxMoves - dis[u], maxMoves - dis[v]，这就是细分节点的个数
    - 需要注意两点：1，maxMoves不一定比dis[u]大；2，若从u和v出发加起来的细分节点数大于uv之间所有的细分节点，记得clamp到uv之间的细分节点个数

2 回顾dijstra算法：

unordered_map<int, unordered_map<int, int>> g;
        
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        for(auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            g[u][v] = w+1;
            g[v][u] = w+1;
        }

        // init dis
        vector<int> disRes(n, INT_MAX);
        map<int, bool> visited;
        visited[0] = true;
        disRes[0] = 0;
        pq.push({0, 0});

        // contain 0 itSelf!

        int res = 0; 


        // dijstra
        while(pq.size() > 0) {
            auto node = pq.top();
            pq.pop();
            int u = node.second;
            int dis = node.first;

            // for disRes[u], every relax will push a new pair, so we need
            // to pass all old relaxed value
/**
 * 
 * eg: [[2,3,4],[1,3,9],[0,2,4],[0,1,1]]
 * 对于上图的dijstra的距离表的松弛过程为：
0 2 2147483647 2147483647 
0 2 5 2147483647 
0 2 5 12 // 这里，第一次松弛来自节点1，
0 2 5 10 // 第二次来自节点2，那么这两个松弛结果都会记录在pq里面，为了让后面
         // pq遍历到 0到3距离为12的时候能pass掉，我么你需要将12和  10(存于距离中)做比较，
         // 就可以直到12是第一次松弛的结果，10才是最终松弛的结果，否则如果还有其他节点，
         // 那么12会在10松弛完其他节点接着松弛，那就错了
         // 于是这个continue是必要的
*/
            if(disRes[u] < dis) {
                continue;
            }
            visited[u] = true;
            disRes[u] = dis;
            
            res += (disRes[u] <= maxMoves);

            // relax nodes by u
            for(auto& neighbor : g[u]) {
                int v = neighbor.first;
                int w = neighbor.second;
                // v has been proceed!
                if(!visited[v] && disRes[v] > disRes[u] + g[u][v]) {
                    disRes[v] = disRes[u] + g[u][v];
                    pq.push({disRes[v], v});
                    // print(disRes);
                }
           }
};

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        unordered_map<int, unordered_map<int, int>> g;
        
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        for(auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            g[u][v] = w+1;
            g[v][u] = w+1;
        }

        // init dis
        vector<int> disRes(n, INT_MAX);
        map<int, bool> visited;
        visited[0] = true;
        disRes[0] = 0;
        pq.push({0, 0});
        // disRes[0] = 0;
        // for(auto& neighbor : g[0]) {
        //     int to = neighbor.first;
        //     int w = neighbor.second
        //     disRes[to] = w;
        //     pq.push({w, to});
        // }

        // contain 0 itSelf!
        int res = 0; 


        // dijstra
        while(pq.size() > 0) {
            auto node = pq.top();
            pq.pop();
            int u = node.second;
            int dis = node.first;

            // for disRes[u], every relax will push a new pair, so we need
            // to pass all old relaxed value
            if(disRes[u] < dis) {
                continue;
            }
            visited[u] = true;
            disRes[u] = dis;
            
            res += (disRes[u] <= maxMoves);

            // relax nodes by u
            for(auto& neighbor : g[u]) {
                int v = neighbor.first;
                int w = neighbor.second;
                // v has been proceed!
                if(!visited[v] && disRes[v] > disRes[u] + g[u][v]) {
                    disRes[v] = disRes[u] + g[u][v];
                    pq.push({disRes[v], v});
                    print(disRes);
                }
            }
        }

        // count sub nodes
        for(auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            int curSubNodes = 0;
            if(visited[u]) {
                curSubNodes += max(maxMoves - disRes[u], 0);
            }
            if(visited[v]) {
                curSubNodes += max(maxMoves - disRes[v], 0);
            }
            curSubNodes = min(curSubNodes, w);
            // cout << "curSub/edge: " << curSubNodes << " " << "e: " << u << "->" << v << endl;
            res += curSubNodes;
        }


        return res;
    }
    void print(vector<int>& dis) {
        for(int i = 0; i < dis.size(); ++i) {
            cout <<dis[i] << " ";
        }cout << "\n";
    }
};

1368minCostToHaveAPath 使网格图至少有一条有效路径的最小代价

1 题目

https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

2 解题思路

1 解题思路：
- 1.1 说明思路：构图，正确方向，那么u到v的距离为0，否则为1
  - 那么不就求从00到mn的最短路吗？dijstra可以做
- 1.2 但是你非要用bfs：
  - 解决办法也简单，此时决定一个点v是否进入下一次bfs不再是vis数组了，而是：用dis[u]表示从0到u的距离，然后它的邻居v们，是否进入下一次bfs，是由：dis[v] < dis[u] + g[u][v].weight，也就是如果v被松弛了，进入下一次bfs，这个和dijstra思想基本上是一样的，但是可能有很多重复计算
- 1.3 这个叫01bfs，也就是说，队列里的点，到原点的距离，要么是dis，要么是dis+1，当然是使用deque维护，g[u][v].weight如果为1，从队尾进入，否则从对首进入，但是不这么做貌似也行哈哈哈，就用普通的队列即可

class Solution {
public:
    int dx[4] = {1,-1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;

    int bfs(vector<vector<pair<int, int>>>& g) {
        // start from 0, search first 0 wighted edges
        deque<pair<int, int>> curLevel; // <node, dis from 0,0>
        curLevel.push_front({0, 0});
        vector<bool> vis(m*n); 
        vector<int> disV(m*n, INT_MAX); 
        disV[0] = 0;
        int tar =  m * n - 1;
        
        
        int res = INT_MAX;
        while(0 != curLevel.size()) {
            // cout << "---" << endl;
            int curLevelSize = curLevel.size();
            while(curLevelSize-- > 0) {
                auto curNode = curLevel.front();
                curLevel.pop_front();
                // cout << curNode.first << "-> dis: " << curNode.second << endl;

                int curDis = disV[curNode.first];
                for(auto& [neighbor, dis] : g[curNode.first]) {
                    // cout << "from/to: " << curNode.first << "/ " << neighbor << endl;
                    int newDis = curDis + dis;
                    if(newDis < disV[neighbor]) {
                        curLevel.push_back({neighbor, dis});
                        // if(dis == 0) {
                        //     curLevel.push_front({neighbor, 0});
                        // } else {
                        //     curLevel.push_back({neighbor, 1});
                        // }
                        disV[neighbor] = newDis;
                    }
                    if(neighbor == tar) { 
                        res = min(res, disV[tar]); 
                    }
                }
            }
        }

        return res == INT_MAX ? 0 : res;
    }

    int minCost(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<pair<int, int>>> g(m * n);

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                int curNode = j + i * n;
                // cout << "i/j" << i << " " << j << endl;
                for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
                    int nextI = i + dy[mvIdx];
                    int nextJ = j + dx[mvIdx];
                    if(0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n) {
                        int nextNode = nextI * n + nextJ;
                        // cout << mvIdx << endl;
                        if(grid[i][j] == mvIdx + 1) {
                            g[curNode].push_back({nextNode, 0});
                            // cout << "to " << nextNode << " = " << 0 << " ";
                        } else {
                            g[curNode].push_back({nextNode, 1});
                            // cout << "to " << nextNode << " = " << 1 << " ";
                        }
                        // cout << "\n";
                    }
                }
                sort(g[curNode].begin(), g[curNode].end(), 
                    [](const pair<int, int>& a, const pair<int, int>& b) {
                        return a.second < b.second;
                });
            }
        }

        // bfs to get dis
        return bfs(g);
    }
}

1579maxNumEdgeToRemove 保证图可完全遍历的最大删除边数

1 题目

https://leetcode.cn/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/

2 解题思路

1 解题思路：（不如说：并查集就是典型的逆向思维）
- 1.1 不要顺着考虑删除边的情况，那样式2^n复杂度，解决不了问题，逆向思维，考虑一条条加入边
- 1.2 肯定是优先加入公共边，若能merge则是有用边，否则为无用边，则++res，然后看是否连通，如果连通，就不用alice和bob的专业边了，可以直接返回结果
- 1.3 不然的话，要分别考虑alice和bob，对alice来说，从上面1.2中得到的并查集，对每一条a边尝试加入，失败则++res，对bob同样如此，最后返回res，当然失败情况就是，alice和bob至少有一个人的并查集的root数目大于1；

class Solution {
public:
    
    class UF {
    public: 
        int rootNums;
        vector<int> parent;

        UF(int size) : rootNums(size - 1) {
            for(int i = 0; i < size; ++i) {
                parent.push_back(i);
            }
        }
        
        int find(int x) {
            int oldX = x;
            while(x != parent[x]) {
                // parent[x] = parent[parent[x]]; // compression path
                x = parent[x];
            }
            parent[oldX] = x; // the same as upwards
            return x;
        }

        bool merge(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                parent[rootX] = rootY;
                --rootNums;
                return true;
            }
            return false;
        }
    };
    
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        vector<vector<int>> aEdges;
        vector<vector<int>> bEdges;
        vector<vector<int>> abEdges;

        for(auto& e : edges) {
            if(1 == e[0]) {
                aEdges.push_back(e);
            } else if(2 == e[0]) {
                bEdges.push_back(e);
            } else  {
                abEdges.push_back(e);
            }
        }

        int removeEdgeCnt = 0;
        
        UF uf(n + 1);
        int abCnt = 0;
        // firstly add the common edges
        for(auto& e : abEdges) {
            if(!uf.merge(e[1], e[2])) {
                // cout << "ab: rm: " << e[1] << "-" << e[2] << endl;  
                ++removeEdgeCnt;
            } else {
                // cout << "ab: merge: " << e[1] << "-" << e[2] << endl;  
                ++abCnt;
            }
        }

        if(1 == uf.rootNums) {
            return edges.size() - abCnt;
        }
//  cout << "cur rmAB cnt: " << removeEdgeCnt << endl;
        UF ufA = uf;
        UF ufB = uf;
        // try to make alice all ok
        int aCnt = 0;
        for(auto& e : aEdges) {
            if(!ufA.merge(e[1], e[2])) {
                ++removeEdgeCnt;
                // cout << "a: rm: " << e[1] << "-" << e[2] << endl;  
            } 
        }
        // cout << "cur rmA cnt: " << removeEdgeCnt << endl;

        // try to make bob all ok
        int bCnt = 0;
        for(auto& e : bEdges) {
            if(!ufB.merge(e[1], e[2])) {
                ++removeEdgeCnt;
                // cout << "b: rm: " << e[1] << "-" << e[2] << endl;  
            }
        }

        //  cout << "cur rmB cnt: " << removeEdgeCnt << endl;
        if(1 == ufB.rootNums && 1 == ufA.rootNums) {
            return removeEdgeCnt;
        }
        return -1;
    }
};

1928minCostToReachInMaxTime 规定时间内到达终点的最小花费

1 题目

https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/

2 解题思路

1 解题思路：动态规划：
- f[t][i]: fees in exact time t to reach node i
- f[t][i] = min(f[t - time(j, i)][j] + fee[i])

class Solution {
public:
    using pii = pair<int, int>; 
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        // build g
        int n = passingFees.size();
        vector<vector<pii>> g(n);
        for(auto&e : edges) {
            g[e[0]].push_back({e[1], e[2]});
            g[e[1]].push_back({e[0], e[2]});
        }


        // f[t][i]: fees in exact time t to reach node i
        int res = INT_MAX;
        vector<vector<int>> f(maxTime+1, vector<int>(n, INT_MAX));
        f[0][0] = passingFees[0];
        // f[t][i] = min(f[t - time(j, i)][j] + fee[i])
        for(int t = 1; t <= maxTime; ++t) {
            for(int i = 1; i < n; ++i) {
                for(auto& [j, time] : g[i]) {
                    if(t - time >= 0 && f[t-time][j] != INT_MAX) {
                        f[t][i] = min(f[t][i], f[t - time][j] + passingFees[i]);
                    }
                }
            }
        }

        for(int t = 1; t <= maxTime; ++t) {
            res = min(res, f[t][n-1]);
        }

        return res == INT_MAX ? -1 : res;
    }
}

2065maxPathValueWithinMaxtime 规定时间内路径的最大价值

1 题目

https://leetcode.cn/problems/maximum-path-quality-of-a-graph/

2 解题思路

1 解题思路：
- 1.1 考虑一个问题：如何遍历所有路径？那不就是回溯吗，对于u，尝试v进入下一个dfs，然后dfs完成v以后尝试下一个v，将之前的v设置为未访问即可
- 1.2 那么什么时候更新结果？只要v == 0并且剩余时间 >= 0,就可以更新结果
- 1.3 那什么时候返回？时间小于0了就返回啊
- 1.4 有个问题，要求路径中节点的值不被重复加？那不就是回溯过程中，如果当前顶点v被用过，那么直接从v进入dfs，就不去将当前v的价值考虑进去就行，而且也不需要去标记它没被访问过，因为它是已经被访问过的节点（走回头路了嘛），因为只有一个地方可以回溯，那么就是进入v且v此时没有被访问过然后dfs完成以后可以将v置为未访问

class Solution {
public:
    long long n;
    using pii = pair<long long, long long>;

    void dfs(unordered_map<long long, vector<pii>>& g, long long st, long long leftTime, vector<int>& values, vector<bool>& used, long long& res, long long& curValue) {
        // even the time cost least node not able to reach
        // cout << "at node/lefttime" << st << "/" << leftTime << endl;

        if(0 == st && leftTime >= 0) {
            res = max(res, curValue);
        }

        if(leftTime < 0) {
            return ;
        }

        for(auto& [v, w] : g[st]) {

            if(!used[v]) {
                // cout << "u->v: " << st << "->" << v << endl;
                used[v] = true;
                curValue += values[v];

                dfs(g, v, leftTime - w, values, used, res, curValue);

                // cout << "use new node: maxValue is : " << res << endl;
                curValue -= values[v];
                used[v] = false;
            } else {

                dfs(g, v, leftTime - w, values, used, res, curValue);
                // cout << "use new node: maxValue is : " << res << endl;
            }
        }
    }

    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        n =  values.size();

        unordered_map<long long, vector<pii>> g(n);
        for(auto& e : edges) {
            long long u = e[0];
            long long v = e[1];
            long long w = e[2];

           g[u].push_back({v, w});
           g[v].push_back({u, w});
        }
        
        // smallest weighted edge first
        for(auto& [node, neighbors] : g) {
            sort(neighbors.begin(), neighbors.end(), [](const pii& a, const pii& b) {
                return a.second < b.second;
            });
        }
        vector<bool> vecBool(n, false);
        vecBool[0] = true;

        long long res = INT_MIN;
        long long curValue = values[0];

        if(0 == g[0].size()) {
            return values[0];
        }

        dfs(g, 0, maxTime, values, vecBool, res, curValue);
        return res;
    }
};

0 图常见算法

trajan 塔杨算法 求割点(关键点)，割边

1192criticalConnections 查找集群内的「关键连接」

1 题目

2 解题思路

tarjan求连通子集

1 题集

0882reachableSubNodes 细分图中的可到达结点 dijstra

1 题目

2 解题思路

1368minCostToHaveAPath 使网格图至少有一条有效路径的最小代价

1 题目

2 解题思路

1579maxNumEdgeToRemove 保证图可完全遍历的最大删除边数

1 题目

2 解题思路

1928minCostToReachInMaxTime 规定时间内到达终点的最小花费

1 题目

2 解题思路

2065maxPathValueWithinMaxtime 规定时间内路径的最大价值

1 题目

2 解题思路

trajan 塔杨算法求割点(关键点)，割边