Kết nối dự phòng trong C ++

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, ]