DAY 9
0
Software Development

## 8.5 一些 Leetcode 例子

### Leetcode 1192. Critical Connections in a network

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

``````class Solution {
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
for(auto e : connections) {
}
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;
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

``````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;
}
};
``````