ช่วงเวลาที่เร็วที่สุดเมื่อทุกคนกลายเป็นเพื่อนกันใน C++

สมมติว่าในกลุ่มสังคม มี N คนที่แตกต่างกัน โดยมีรหัสจำนวนเต็มที่ไม่ซ้ำกันตั้งแต่ 0 ถึง N-1 ที่นี่ เรามีรายการบันทึก โดยแต่ละ logs[i] =[time, id_A, id_B] มีการประทับเวลาของจำนวนเต็มไม่เป็นลบ และรหัสของคนสองคนที่แตกต่างกัน บันทึกแต่ละรายการจะแสดงเวลาที่คนสองคนกลายเป็นเพื่อนกัน ถ้า A เป็นเพื่อนกับ B แล้ว B คือเพื่อนกับ A สมมุติว่า A สนิทกับ B ถ้า A เป็นเพื่อนกับ B หรือ A เป็นเพื่อนของคนที่รู้จัก B เราต้องหาเวลาให้เร็วที่สุด ที่ทุกคนคุ้นเคยกันดี หากไม่พบเวลาดังกล่าว ให้คืนค่า -1 ดังนั้นหากอินพุตมีลักษณะดังนี้:[[20190101,0,1], [20190104,3,4], [20190107,2,3], [20190211,1,5] , [20190224,2,4], [20190301,0,3], [20190312,1,2], [20190322,4,5]], N =6, ผลลัพธ์จะเป็น 20190301 เนื่องจากเหตุการณ์แรกเกิดขึ้น ที่ประทับเวลา =20190101 และหลังจากที่บุคคลที่ 0 และ 1 กลายเป็นเพื่อนกัน เราก็มีกลุ่มมิตรภาพ [0,1], [2], [3], [4], [5] จากนั้นเหตุการณ์ที่สองจะเกิดขึ้นที่ timestamp =20190104 และหลังจากที่บุคคลที่ 3 และ 4 กลายเป็นเพื่อนกัน เรามีกลุ่มมิตรภาพดังต่อไปนี้ [0,1], [2], [3,4], [5] หลังจากนั้นเหตุการณ์ที่สามจะเกิดขึ้นที่เวลาประทับ =20190107 และหลังจากที่บุคคลที่ 2 และ 3 กลายเป็นเพื่อนกัน เรามีกลุ่มมิตรภาพดังต่อไปนี้ [0,1], [2,3,4], [5] จากนั้นเหตุการณ์ที่สี่เกิดขึ้นที่ timestamp =20190211 และหลังจากที่บุคคลที่ 1 และ 5 กลายเป็นเพื่อนกัน เรามีกลุ่มมิตรภาพดังต่อไปนี้ [0,1,5], [2,3,4] หลังจากเหตุการณ์ที่ 5 เกิดขึ้น ณ เวลาประทับ =20190224 และเนื่องจากบุคคลที่ 2 และ 4 เป็นเพื่อนกันแล้ว อะไรก็เกิดขึ้นได้ สุดท้าย เหตุการณ์ที่หกเกิดขึ้นที่ timestamp =20190301 และหลังจากที่บุคคลที่ 0 และ 3 กลายเป็นเพื่อนกัน เราก็กลายเป็นเพื่อนกัน

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

• กำหนดวิธีการที่เรียกว่า find() ซึ่งจะใช้ค่า x ซึ่งจะทำงานดังนี้ −

• ถ้า parent[x] คือ -1 ให้คืนค่า x

• พ่อแม่[x] :=find(parents[x])

• ส่งคืนผู้ปกครอง[x]

• โดยวิธีการหลักจะทำงานดังนี้ −

• กำหนดอาร์เรย์สองอาร์เรย์ที่เรียกว่าพาเรนต์และอันดับ ขนาด N เติมพาเรนต์ด้วย -1 และเติมอันดับด้วย 1 วินาที

• จัดเรียงบันทึก

• สำหรับแต่ละองค์ประกอบ i ในบันทึก -

  • ดำเนินการสหภาพบน i[1] และ i[2]

  • find(i[2]) และ find(i[1])

  • ถ้า N อยู่ในอาร์เรย์อันดับ ให้ส่งคืน i[0]

• กลับ -1

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int earliestAcq(vector<vector<int>>& logs, int N) {
      vector<int> ds (N, -1);
      sort(begin(logs), end(logs));
      for(vector<int> &k : logs) {
         if(un(k[1], k[2], ds) == N) return k[0];
      }
      return -1;
   }
   int un(int u, int v, vector<int> & ds) {
      u = find(u, ds);
      v = find(v, ds);
      if(u != v) {
         ds[v] += ds[u];
         ds[u] = v;
      }
      return -ds[v];
   }
   int find(int u, vector<int> & ds) {
      return ds[u] < 0? u : ds[u] = find(ds[u], ds);
   }
};
main(){
   vector<vector<int>> v = {
      {20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},
      {20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}
   };
   Solution ob;
   cout <<ob.earliestAcq(v, 6);
}

อินพุต

[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],
[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]]
6

ผลลัพธ์

20190301