C++-এ সবাই বন্ধু হয়ে যাওয়ার সবচেয়ে আগের মুহূর্ত

মনে করুন একটি সোশ্যাল গ্রুপে Nজন ভিন্ন মানুষ আছে, যাদের ইউনিক ইন্টিজার আইডি ০ থেকে 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], [2], [3], [4], [5]। দ্বিতীয় ইভেন্ট 20190104-এ, ৩ ও ৪ বন্ধু হয়: [0,1], [2], [3,4], [5]। তৃতীয় ইভেন্ট 20190107-এ, ২ ও ৩ বন্ধু হয়: [0,1], [2,3,4], [5]। চতুর্থ ইভেন্ট 20190211-এ, ১ ও ৫ বন্ধু হয়: [0,1,5], [2,3,4]। পঞ্চম ইভেন্ট 20190224-এ, ২ ও ৪ ইতিমধ্যে বন্ধু তাই কিছু হয় না। শেষে ছয়ième ইভেন্ট 20190301-এ, ০ ও ৩ বন্ধু হয়ে সবাই পরিচিত হয়ে যায়।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (Union-Find / Disjoint Set Union):

• find(x) মেথড ডিফাইন করুন:

  • যদি parents[x] == -1, তবে return x

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

  • return parents[x]

• মেইন মেথড:

  • parents এবং rank দুই অ্যারে সাইজ N, parents -1 দিয়ে, rank ১ দিয়ে পূরণ।

  • logs সর্ট করুন।

  • প্রতিটি i in logs জন্য:

    • i[1] এবং i[2]-তে ইউনিয়ন করুন।

    • find(i[2]) এবং find(i[1])

    • যদি N rank অ্যারেতে থাকে, তবে i[0] রিটার্ন করুন।

  • return -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);
    }
};

int 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 << 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