सबसे शुरुआती पल जब C++ में हर कोई दोस्त बन जाता है

मान लीजिए एक सामाजिक समूह में, 0 से N-1 तक अद्वितीय पूर्णांक आईडी वाले N अलग-अलग लोग हैं। यहां हमारे पास लॉग की एक सूची है, जहां प्रत्येक लॉग [i] =[समय, 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 के दोस्त बनने के बाद हमारे पास सभी दोस्त बन जाते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• खोज () नामक एक विधि को परिभाषित करें, यह एक मान x लेगा, यह निम्नानुसार काम करेगा -

• अगर माता-पिता [x] -1 है, तो x लौटाएं

• माता-पिता [x]:=ढूंढें (माता-पिता [x])

• माता-पिता को लौटाएं[x]

• मुख्य विधि में यह निम्न प्रकार से कार्य करेगा-

• माता-पिता और रैंक नामक दो सरणियों को परिभाषित करें, आकार N, माता-पिता को -1 से भरें, और रैंक को 1s से भरें

• लॉग सॉर्ट करें

• लॉग में प्रत्येक तत्व i के लिए -

  • 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