Giả sử có n máy chủ. Chúng được đánh số từ 0 đến n-1 và được kết nối bởi các kết nối máy chủ-máy chủ vô hướng membentuk một mạng lưới, trong đó connections[i] = [a,b] biểu diễn một kết nối giữa máy chủ a và b. Tất cả các máy chủ đều được kết nối trực tiếp hoặc thông qua các máy chủ khác. Bây giờ, một kết nối quan trọng là một kết nối mà, nếu bị xóa, sẽ khiến một số máy chủ không thể truy cập được máy chủ khác. Chúng ta phải tìm tất cả các kết nối quan trọng.
Vì vậy, nếu đầu vào giống như n = 4 và connection = [[0,1],[1,2],[2,0],[1,3]],
thì đầu ra sẽ là [[1,3]]
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa một tập hợp
Định nghĩa mảng disc
Định nghĩa mảng low
Định nghĩa mảng 2D ret
Định nghĩa hàm dfs(), nhận node, par, mảng 2D graph,
nếu node có trong visited, thì −
trả về
chèn node vào visited
disc[node] := time
low[node] := time
(tăng time lên 1)
cho tất cả phần tử x trong graph[node]
nếu x bằng par, thì −
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
nếu x không có trong visited, thì −
dfs(x, node, graph)
low[node] := min của low[node] và low[x]
nếu disc[node] < low[x], thì −
chèn { node, x } vào cuối ret
Ngược lại
low[node] := min của low[node] và disc[x]
Từ phương thức main, thực hiện như sau −
đặt kích thước disc là n + 1
đặt kích thước low là n + 1
time := 0
Định nghĩa mảng danh sách kích thước graph n + 1
for khởi tạo i := 0, khi i < kích thước của v, cập nhật (tăng i lên 1), thực hiện −
u := v[i, 0]
w := v[i, 1]
chèn w vào cuối graph[u]
chèn u vào cuối graph[w]
dfs(0, -1, graph)
trả về ret
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: set<int> visited; vector<int> disc; vector<int> low; int time; vector<vector<int> > ret; void dfs(int node, int par, vector<int> graph[]) { if (visited.count(node)) return; visited.insert(node); disc[node] = low[node] = time; time++; for (int x : graph[node]) { if (x == par) continue; if (!visited.count(x)) { dfs(x, node, graph); low[node] = min(low[node], low[x]); if (disc[node] < low[x]) { ret.push_back({ node, x }); } } else{ low[node] = min(low[node], disc[x]); } } } vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) { disc.resize(n + 1); low.resize(n + 1); time = 0; vector<int> graph[n + 1]; for (int i = 0; i < v.size(); i++) { int u = v[i][0]; int w = v[i][1]; graph[u].push_back(w); graph[w].push_back(u); } dfs(0, -1, graph); return ret; } }; main(){ Solution ob; vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}}; print_vector(ob.criticalConnections(4,v)); } Đầu vào
4, {{0,1},{1,2},{2,0},{1,3}} Đầu ra
[[1, 3, ],]