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] हैं। फिर दूसरी घटना टाइमस्टैम्प = 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 लेगा, यह निम्नानुसार काम करेगा -

• यदि parents[x] -1 है, तो x लौटाएं

• parents[x] := find(parents[x])

• parents[x] लौटाएं

• मुख्य मेथड में, यह निम्नानुसार काम करेगा -

• parents और rank नामक दो ऐरे परिभाषित करें, आकार N के, parents को -1 से भरें, और rank को 1s से भरें

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

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

  • i[1] और i[2] पर यूनियन करें

  • find(i[2]) और find(i[1])

  • यदि N rank ऐरे में है, तो i[0] लौटाएं

• -1 लौटाएं

उदाहरण (C++)

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

#include 
using namespace std;
class Solution {
    public:
    int earliestAcq(vector>& logs, int N) {
        vector ds (N, -1);
        sort(begin(logs), end(logs));
        for(vector &k : logs) {
            if(un(k[1], k[2], ds) == N) return k[0];
        }
        return -1;
    }
    int un(int u, int v, vector & 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 & ds) {
        return ds[u] < 0? u : ds[u] = find(ds[u], ds);
    }
};
main(){
    vector> 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 <
इनपुट
[[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