資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的冗餘連線 II
假設我們有一棵有根樹。這是一個有向圖，只有一個節點（根節點），所有其他節點都是這個節點的後代，並且除根節點外，每個節點只有一個父節點。根節點沒有父節點。
在給定的輸入中，一個有向圖，它最初是一個有N個節點的有根樹（所有值都是唯一的），並添加了一條額外的有向邊。新增的邊是從1到N中選擇的兩個不同的頂點，並且不是已經存在的邊。
圖將是一個二維邊的陣列。邊的每個元素都是一個類似於[u, v]的pair，表示連線節點u和v的有向邊，其中u是子節點v的父節點。
我們必須找到一條可以移除的邊，以便生成的圖成為一個有N個節點的有根樹。可能有多個答案，我們必須返回在給定二維陣列中最後出現的答案。
因此，如果輸入如下：
輸出將是 [2,3]
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 getParent()，它將接收節點和一個父節點陣列。
- 如果 parent[node] 等於 -1，則：
- 返回 node
- 返回 parent[node] = getParent(parent[node], parent)
- 在主方法中，執行以下操作：
- n := edges 的大小
- 定義一個大小為 n + 5 的父節點陣列，並將其填充為 -1
- 定義一個大小為 n + 5 的 ds 陣列，並將其填充為 -1
- last := -1, second := -1, first := -1
- 對於初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
- u := edges[i, 0], v := edges[i, 1]
- 如果 parent[v] 不等於 -1，則：
- first := parent[v]
- second := i
- 忽略以下部分，跳到下一個迭代
- parent[v] := i, parentU := getParent(u, ds), parentV := getParent(v, ds)
- 如果 parentU 等於 parentV，則：
- last := i
- 否則：
- ds[parentV] := parentU
- 如果 last 等於 -1，則：
- 返回 edges[second]
- 如果 second 等於 -1，則：
- 返回 edges[last]
- 返回 edges[first]
讓我們看看以下實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int getParent(int node, vector <int>& parent){
if(parent[node] == -1)return node;
return parent[node] = getParent(parent[node], parent);
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector <int> parent(n + 5, -1);
vector <int> ds(n + 5, -1);
int last = -1, second = -1, first = -1;
int u, v;
int parentU, parentV;
for(int i = 0; i < n; i++){
u = edges[i][0];
v = edges[i][1];
if(parent[v] != -1){
first = parent[v];
second = i;
continue;
}
parent[v] = i;
parentU = getParent(u, ds);
parentV = getParent(v, ds);
if(parentU == parentV){
last = i;
}else ds[parentV] = parentU;
}
if(last == -1)return edges[second];
if(second == -1)return edges[last];
return edges[first];
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{2,3}};
print_vector(ob.findRedundantDirectedConnection(v));
}輸入
{{1,2},{1,3},{2,3}}輸出
[2, 3, ]
更新於：2020年6月1日
176 次瀏覽
廣告