資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++網路中的關鍵連線
假設有n臺伺服器，編號從0到n-1，由伺服器到伺服器的無向連線構成一個網路，其中connections[i] = [a,b]表示伺服器a和b之間的連線。所有伺服器都直接或透過其他伺服器連線。關鍵連線是指如果移除該連線，則會使某些伺服器無法到達其他伺服器的連線。我們需要找到所有關鍵連線。
例如，如果輸入n = 4，connection = [[0,1],[1,2],[2,0],[1,3]]，
則輸出為[[1,3]]
為了解決這個問題，我們將遵循以下步驟：
定義一個集合
定義一個數組disc
定義一個數組low
定義一個二維陣列ret
定義一個函式dfs()，它將接收節點、父節點、一個二維陣列graph作為引數。
如果節點已在visited中：
返回
將節點插入visited
disc[node] := time
low[node] := time
(time加1)
對於graph[node]中的所有元素x
如果x等於父節點：
忽略以下部分，跳到下一個迭代
如果x不在visited中：
dfs(x, node, graph)
low[node] := low[node]和low[x]的最小值
如果disc[node] < low[x]：
將{node, x}插入ret的末尾
否則
low[node] := low[node]和disc[x]的最小值
在主方法中，執行以下操作：
將disc的大小設定為n + 1
將low的大小設定為n + 1
time := 0
定義一個大小為graph n + 1的列表陣列
初始化i := 0，當i < v的大小，更新(i加1)，執行：
u := v[i, 0]
w := v[i, 1]
將w插入graph[u]的末尾
將u插入graph[w]的末尾
dfs(0, -1, graph)
返回ret
讓我們看下面的實現來更好地理解：
示例
#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));
}輸入
4, {{0,1},{1,2},{2,0},{1,3}}輸出
[[1, 3, ],]
387 次瀏覽
