การเชื่อมต่อซ้ำซ้อน II ใน C ++

สมมติว่าเรามีต้นไม้ที่หยั่งรากแล้ว นี่คือกราฟกำกับที่มีเพียงโหนดเดียว (ซึ่งเป็นรูท) ซึ่งโหนดอื่นทั้งหมดเป็นลูกหลานของโหนดนี้ และทุกโหนดมีพาเรนต์เพียงคนเดียว ยกเว้นโหนดรูท รูทไม่มีพ่อแม่

ในอินพุตที่กำหนด กราฟกำกับที่เริ่มต้นเป็นทรีที่รูตด้วยโหนด N (ค่าทั้งหมดไม่ซ้ำกัน) โดยเพิ่มขอบกำกับเพิ่มเติมหนึ่งรายการ ขอบที่เพิ่มเข้ามามีจุดยอดที่แตกต่างกันสองจุดที่เลือกจาก 1 ถึง N และไม่ใช่ขอบที่มีอยู่แล้ว

กราฟจะเป็นอาร์เรย์ 2 มิติของขอบ องค์ประกอบของขอบแต่ละอันเป็นคู่เช่น [u, v] ที่แสดงถึงขอบตรงที่เชื่อมต่อโหนด u และ v โดยที่ u เป็นพาเรนต์ของลูก v.

เราต้องหาขอบที่สามารถลบออกได้เพื่อให้กราฟที่ได้เป็นต้นไม้ที่รูทของโหนด N อาจมีหลายคำตอบ เราต้องส่งคืนคำตอบสุดท้ายในอาร์เรย์ 2 มิติที่กำหนด

ดังนั้นหากอินพุตเป็นแบบ −

ผลลัพธ์จะเป็น [2,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน getParent() ซึ่งจะใช้โหนด พาเรนต์อาร์เรย์
• ถ้า parent[node] เหมือนกับ -1 แล้ว −
  • โหนดส่งคืน
• ส่งคืนพาเรนต์[โหนด] =getParent(พาเรนต์[โหนด], พาเรนต์)
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• n :=ขนาดของขอบ
• กำหนดอาร์เรย์หลักที่มีขนาด n + 5 เติมด้วย -1
• กำหนดอาร์เรย์ ds ขนาด n + 5 เติมด้วย -1
• สุดท้าย :=-1 วินาที :=- 1 แรก :=- 1
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• u :=Edge[i, 0], v :=Edge[i, 1]
• ถ้า parent[v] ไม่เท่ากับ -1 แล้ว −
  • ก่อน :=parent[v]
  • วินาที :=ฉัน
  • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
• พาเรนต์[v] :=i, parentU :=getParent(u, ds), parentV :=getParent(v, ds)
• ถ้า parentU เหมือนกับ parentV แล้ว −
  • สุดท้าย :=ฉัน
• มิฉะนั้น
  • ds[parentV] :=parentU

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

[2, 3, ]