数据结构
网络
关系数据库管理系统 (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
