뿌리가 없는 나무가 하나 있다고 가정합니다. 이것은 주기가 없는 하나의 무방향 그래프입니다. 주어진 입력은 하나의 추가 에지가 추가된 N개의 노드(노드의 값은 1에서 N까지의 고유한 값임)가 있는 트리로 시작된 그래프입니다. 추가된 가장자리는 1에서 N까지 선택된 두 개의 다른 정점을 가지며 이미 존재하는 가장자리가 아닙니다.
최종 그래프는 에지의 2D 배열로 제공됩니다. 모서리의 각 요소는 쌍 [u, v]입니다. 여기서 u
결과 그래프가 N 노드의 트리가 되도록 제거할 수 있는 간선을 찾아야 합니다. 여러 답변이 있을 수 있으므로 주어진 2Darray에서 마지막으로 발생하는 답변을 찾아야 합니다. 답변 가장자리 [u, v]는 u
따라서 입력이 [[1,2], [2,3], [3,4], [1,4], [1,5]],
그러면 출력은 [1,4]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
N :=1000
N+5 크기의 배열 부모를 정의합니다.
N+5 크기의 배열 순위를 정의합니다.
getParent() 함수를 정의하면 n이 필요합니다.
부모[n]이 -1과 같으면 -
반환 n
부모[n] 반환 =getParent(부모[n])
Unionn() 함수를 정의하면, b,
pa :=getParent(a), pb :=getParent(b)
pa가 pb와 같으면 -
거짓을 반환
rank[pa]> rank[pb]이면 -
순위[pa] :=순위[pa] + 순위[pb]
부모[pb] :=파
그렇지 않으면
순위[pb] :=순위[pb] + 순위[pa]
부모[pa] :=pb
true를 반환
기본 방법에서 다음을 수행하십시오 -
n :=에지 목록의 크기
initialize i :=0의 경우, i
부모[가장자리[i, 0]] :=-1, 부모[가장자리[i, 1]] :=- 1
순위[가장자리[i, 0]]:=-1, 순위[가장자리[i, 1]]:=1
배열 정의
initialize i :=0의 경우, i
u :=가장자리[i, 0]
v :=가장자리[i, 1]
Unionn(u, v)가 0이면 -
as :=가장자리[i]
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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, ]