图的连通 (3)

8.5 一些 Leetcode 例子

今天来拖点稿子，解几题跟连通有关的题目吧。

Leetcode 1192. Critical Connections in a network

https://leetcode.com/problems/critical-connections-in-a-network/
题目大意：给定 n 个点的图，找出所有的关键连线，也就是桥。

解法：首先观察到，所有的桥都会在生成树上，接下来我们只要用 lowpt(x) 来判断哪一些是桥就可以啦。如果是桥的话，那麽子节点底下不存在任何回连边回到祖先。

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> adj(n);
        for(auto e : connections) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        vector<vector<int>> ret;
        map<int, int> lowpt;
        function<void(int, int, int)> dfs = [&](int x, int p=-1, int d=0) {
            lowpt[x] = d;
            for(int y : adj[x]) {
                if (lowpt.find(y) == lowpt.end()) {
                    dfs(y, x, d+1);
                    if (lowpt[y] > d) {
                        ret.push_back({x, y});
                    }   
                }
                if (y != p) {
                    lowpt[x] = min(lowpt[x], lowpt[y]);
                }
            }
        };
        for (int i = 0; i < n; i++) if (lowpt.find(i) == lowpt.end()) {
            dfs(i, -1, 0);
        }
        return ret;
    }
};

Leetcode 1627. Graph Connectivity With Threshold

题目大意：给定一张图 G，每个点的编号是从 1 到 n，若两个点 a 和 b 的最大公因数超过 threashold，就会连一条边。现在问很多问题，问两个点是否属於同一个连通元件。

解法：考虑每一个超过 threadshold 的数字，把所有的倍数都连起来。我们可以用并查集将这些倍数合并成同一组。

class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        vector<int> g(n+1);
        function<int(int)> Find = [&](int x) -> int {
            return g[x]==x? g[x] : (g[x]=Find(g[x]));
        };
        function<void(int, int)> Union = [&](int x, int y) {
            g[Find(x)] = Find(y);
        };
        for(int i=1;i<=n;i++) g[i] = i;
        for(int x=threshold+1;x<=n;x++)
            for(int y = x + x; y <= n; y += x)
                Union(y, y-x);
        vector<bool> ret;
        for(auto e : queries) {
            ret.push_back(Find(e[0])  == Find(e[1]));
        }
        return ret;
    }
};