Giả sử chúng ta có một cây chưa được nhổ; đây là một trong những đồ thị vô hướng không có chu trình. Đầu vào đã cho là một đồ thị bắt đầu dưới dạng cây với N nút (giá trị của các nút là các giá trị khác nhau từ 1 đến N), với một cạnh bổ sung được thêm vào. Cạnh được thêm vào có hai đỉnh khác nhau được chọn từ 1 đến N và không phải là cạnh đã tồn tại.
Đồ thị cuối cùng được cho dưới dạng mảng 2D các cạnh. Mỗi phần tử của các cạnh là một cặp [u, v] trong đó u
Chúng ta phải tìm một cạnh có thể bị loại bỏ để đồ thị kết quả là một cây gồm N nút. Có thể có nhiều câu trả lời, chúng ta phải tìm câu trả lời xuất hiện cuối cùng trong 2Darray đã cho. Cạnh câu trả lời [u, v] phải có cùng định dạng với u
Vì vậy, nếu đầu vào như [[1,2], [2,3], [3,4], [1,4], [1,5]],
thì đầu ra sẽ là [1,4]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=1000
-
Xác định mảng cha có kích thước:N + 5.
-
Xác định thứ hạng mảng có kích thước:N + 5.
-
Xác định một hàm getParent (), điều này sẽ mất n,
-
nếu cha [n] giống -1, thì -
-
trả lại n
-
-
return parent [n] =getParent (parent [n])
-
Xác định một hàm unionn (), điều này sẽ nhận a, b,
-
pa:=getParent (a), pb:=getParent (b)
-
nếu pa giống với pb thì -
-
trả về false
-
-
nếu xếp hạng [pa]> xếp hạng [pb], thì -
-
rank [pa]:=rank [pa] + rank [pb]
-
cha [pb]:=pa
-
-
Nếu không
-
rank [pb]:=rank [pb] + rank [pa]
-
cha [pa]:=pb
-
-
trả về true
-
Từ phương thức chính, thực hiện như sau -
-
n:=kích thước của danh sách cạnh
-
để khởi tạo i:=0, khi i
-
cha [edge [i, 0]]:=-1, cha [edge [i, 1]]:=- 1
-
xếp hạng [cạnh [i, 0]]:=-1, xếp hạng [cạnh [i, 1]]:=1
-
-
Xác định ans mảng
-
để khởi tạo i:=0, khi i
-
u:=edge [i, 0]
-
v:=edge [i, 1]
-
nếu unionn (u, v) bằng 0 thì -
-
ans:=edge [i]
-
-
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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)); }
Đầu vào
{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}
Đầu ra
[1, 4, ]