資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中的冗餘連線
假設我們有一棵無根樹；這是一個沒有環的無向圖。給定的輸入是一個圖，它最初是一棵具有N個節點的樹（節點的值是1到N的不同值），並添加了一條額外的邊。新增的邊有兩個不同的頂點，從1到N選擇，並且不是已經存在的邊。
最終的圖以二維陣列邊的形式給出。edges的每個元素都是一個對[u, v]，其中u < v，表示連線節點u和v的無向邊。
我們必須找到可以移除的一條邊，以便生成的圖是具有N個節點的樹。可能有多個答案，我們必須找到在給定的二維陣列中最後出現的答案。答案邊[u, v]應該採用相同的格式，其中u < v。
因此，如果輸入類似於[[1,2], [2,3], [3,4], [1,4], [1,5]]，
則輸出將為[1,4]
為了解決這個問題，我們將遵循以下步驟：
N := 1000
定義一個大小為N+5的陣列parent。
定義一個大小為N+5的陣列rank。
定義一個函式getParent()，它將接受n，
如果parent[n]等於-1，則：
返回n
返回parent[n] = getParent(parent[n])
定義一個函式unionn()，它將接受a, b，
pa := getParent(a), pb := getParent(b)
如果pa等於pb，則：
返回false
如果rank[pa] > rank[pb]，則：
rank[pa] := rank[pa] + rank[pb]
parent[pb] := pa
否則
rank[pb] := rank[pb] + rank[pa]
parent[pa] := pb
返回true
從主方法中，執行以下操作：
n := edges列表的大小
for 初始化 i := 0, 當 i < n, 更新 (i 增加 1), 執行：
parent[edges[i, 0]] := -1, parent[edges[i, 1]] := -1
rank[edges[i, 0]] := -1, rank[edges[i, 1]] := 1
定義一個數組ans
for 初始化 i := 0, 當 i < n, 更新 (i 增加 1), 執行：
u := edges[i, 0]
v := edges[i, 1]
如果unionn(u, v)為零，則：
ans := edges[i]
返回ans
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
const int N = 1000;
class Solution {
public:
int parent[N + 5];
int rank[N + 5];
int getParent(int n){
if (parent[n] == -1)
return n;
return parent[n] = getParent(parent[n]);
}
bool unionn(int a, int b){
int pa = getParent(a);
int pb = getParent(b);
if (pa == pb)
return false;
if (rank[pa] > rank[pb]) {
rank[pa] += rank[pb];
parent[pb] = pa;
}
else {
rank[pb] += rank[pa];
parent[pa] = pb;
}
return true;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
for (int i = 0; i < n; i++) {
parent[edges[i][0]] = parent[edges[i][1]] = -1;
rank[edges[i][0]] = rank[edges[i][1]] = 1;
}
vector<int> ans;
for (int i = 0; i < n; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (!unionn(u, v)) {
ans = edges[i];
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2}, {2,3}, {3,4}, {1,4}, {1,5}};
print_vector(ob.findRedundantConnection(v));
}輸入
{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}輸出
[1, 4, ]
瀏覽量：301
