প্রথম মুহূর্ত যখন সবাই C++ এ বন্ধু হয়

ধরুন একটি সামাজিক গোষ্ঠীতে, 0 থেকে N-1 পর্যন্ত অনন্য পূর্ণসংখ্যা আইডি সহ N বিভিন্ন লোক রয়েছে। এখানে আমাদের লগগুলির একটি তালিকা রয়েছে, যেখানে প্রতিটি লগ[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]। তারপরে দ্বিতীয় ঘটনাটি ঘটে টাইমস্ট্যাম্প =20190104 এ এবং ব্যক্তি 3 এবং 4 বন্ধু হওয়ার পরে আমাদের নিম্নলিখিত বন্ধুত্ব গ্রুপগুলি রয়েছে [0,1], [2], [3,4], [5]। তারপরে তৃতীয় ঘটনাটি ঘটে টাইমস্ট্যাম্প =20190107 এ এবং ব্যক্তি 2 এবং 3 বন্ধু হওয়ার পরে আমাদের নিম্নলিখিত বন্ধুত্ব গ্রুপগুলি রয়েছে [0,1], [2,3,4], [5]। তারপর চতুর্থ ইভেন্টটি টাইমস্ট্যাম্প =20190211 এ ঘটে এবং ব্যক্তি 1 এবং 5 বন্ধু হওয়ার পরে আমাদের নিম্নলিখিত বন্ধুত্ব গ্রুপগুলি রয়েছে [0,1,5], [2,3,4]। সেখানে পঞ্চম ইভেন্টটি টাইমস্ট্যাম্প =20190224 এ ঘটে এবং 2 এবং 4 ব্যক্তি ইতিমধ্যেই বন্ধু হওয়ায় যে কোনও কিছু ঘটে। অবশেষে, ষষ্ঠ ইভেন্টটি টাইমস্ট্যাম্প =20190301 এ ঘটে এবং ব্যক্তি 0 এবং 3 বন্ধু হওয়ার পরে আমরা সবাই বন্ধু হয়ে যাই।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• find() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি একটি মান x নেবে, এটি নিম্নরূপ কাজ করবে -

• যদি পিতামাতা [x] -1 হয়, তাহলে x

  ফেরত দিন

• পিতামাতা[x] :=খুঁজুন(পিতামাতা[x])

• পিতামাতা ফেরত দিন[x]

• মূল পদ্ধতিতে, এটি নিম্নরূপ কাজ করবে -

• পিতামাতা এবং র্যাঙ্ক নামক দুটি অ্যারে সংজ্ঞায়িত করুন, N আকারের, পিতামাতাকে -1 দিয়ে পূরণ করুন এবং 1s দিয়ে র‌্যাঙ্ক পূরণ করুন

• লগগুলি সাজান

• লগ ইন প্রতিটি উপাদানের জন্য −

  • i[1] এবং i[2]

    -এ মিলন সম্পাদন করুন

  • খুঁজুন(i[2]) এবং খুঁজুন(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