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

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

กราฟสุดท้ายจะได้รับเป็นอาร์เรย์ 2 มิติของขอบ องค์ประกอบของขอบแต่ละอันเป็นคู่ [u, v] โดยที่ u

เราต้องหาขอบที่สามารถลบออกได้เพื่อให้กราฟที่ได้เป็นทรีของโหนด N อาจมีหลายคำตอบ เราต้องหาคำตอบสุดท้ายใน 2Darray ที่ให้มา ขอบคำตอบ [u, v] ควรอยู่ในรูปแบบเดียวกันกับ u

ดังนั้น หากอินพุตเป็นแบบ [[1,2], [2,3], [3,4], [1,4], [1,5]],

แล้วผลลัพธ์จะเป็น [1,4]

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

• ไม่มี :=1,000

• กำหนดขนาดพาเรนต์ของอาร์เรย์:N+5

• กำหนดลำดับขนาดอาร์เรย์:N+5

• กำหนดฟังก์ชัน getParent() ซึ่งจะใช้เวลา n

• ถ้า parent[n] เหมือนกับ -1 แล้ว −

  • กลับ n

• ส่งคืนพาเรนต์[n] =getParent(พาเรนต์[n])

• กำหนดฟังก์ชัน unionn() ซึ่งจะใช้ a, b,

• pa :=getParent(a), pb :=getParent(b)

• ถ้า pa เหมือนกับ pb แล้ว −

  • คืนค่าเท็จ

• ถ้า rank[pa]> rank[pb] แล้ว −

  • อันดับ[pa] :=อันดับ[pa] + อันดับ[pb]

  • ผู้ปกครอง[pb] :=pa

• มิฉะนั้น

  • อันดับ[pb] :=อันดับ[pb] + อันดับ[pa]

  • ผู้ปกครอง[pa] :=pb

• คืนความจริง

• จากวิธีหลัก ให้ทำดังนี้ −

• n :=ขนาดของรายการขอบ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • parent[edges[i, 0]] :=-1, parent[edges[i, 1]] :=- 1

  • อันดับ[ขอบ[i, 0]] :=-1 อันดับ[ขอบ[i, 1]] :=1

• กำหนดอาร์เรย์และ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • u :=edge[i, 0]

  • v :=ขอบ[i, 1]

  • ถ้า unionn(u, v) เป็นศูนย์ ดังนั้น −

    • ตอบ :=ขอบ[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, ]