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

Giả sử chúng ta có một cây có rễ. Đây là một đồ thị có hướng sao cho có chính xác một nút (là nút gốc) mà tất cả các nút khác là con của nút này và mọi nút đều có chính xác một nút cha, ngoại trừ nút gốc. Root không có cha mẹ.

Trong đầu vào đã cho, một đồ thị có hướng bắt đầu dưới dạng cây gốc với N nút (Tất cả các giá trị là duy nhất), với một cạnh có hướng 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ị sẽ là một mảng 2D các cạnh. Mỗi phần tử của các cạnh là một cặp như [u, v] đại diện cho một cạnh có hướng nối các nút u và v, trong đó u là cha của con v.

Chúng ta phải tìm một cạnh có thể được loại bỏ để đồ thị kết quả là một cây gốc gồm N nút. Có thể có nhiều câu trả lời, chúng tôi phải trả lại câu trả lời xuất hiện cuối cùng trong mảng 2D đã cho.

Vì vậy, nếu đầu vào giống như -

Đầu ra sẽ là [2,3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm getParent (), hàm này sẽ lấy nút, một mảng cha mẹ,
• nếu [nút] cha giống -1, thì -
  • nút trả lại
• return cha [node] =getParent (cha [node], cha)
• Từ phương pháp chính, hãy thực hiện như sau -
• n:=kích thước của các cạnh
• Xác định mảng cha có kích thước n + 5, điền vào giá trị này bằng -1
• Xác định một mảng ds có kích thước n + 5, điền vào giá trị này bằng -1
• cuối cùng:=-1, thứ hai:=- 1, thứ nhất:=- 1
• để khởi tạo i:=0, khi i
• u:=edge [i, 0], v:=edge [i, 1]
• nếu cha [v] không bằng -1, thì -
  • đầu tiên:=parent [v]
  • thứ hai:=i
  • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
• parent [v]:=i, parentU:=getParent (u, ds), parentV:=getParent (v, ds)
• nếu parentU giống như parentV, thì -
  • cuối cùng:=i
• Nếu không,
  • ds [parentV]:=parentU

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{{1,2},{1,3},{2,3}}

Đầu ra

[2, 3, ]