পাইথনে শেখানোর জন্য ন্যূনতম মানুষের সংখ্যা খুঁজে বের করার প্রোগ্রাম

আমাদের একটি সংখ্যা n, একটি অ্যারে languages এবং একটি অ্যারে friendships আছে। এখানে n ভাষা আছে ১ থেকে n পর্যন্ত নম্বর করা, languages[i] নির্দেশ করে i-তম ইউজার যেসব ভাষা জানে, এবং friendships[i] একটি জোড়া [ui, vi] ধারণ করে যা ইউজার ui এবং vi-এর মধ্যকার বন্ধুত্ব নির্দেশ করে। আমরা একটি ভাষা সিলেক্ট করতে পারি এবং কিছু ইউজারকে তা শেখাতে পারি যাতে সব বন্ধু একে অপরের সাথে যোগাযোগ করতে পারে। আমাদের শেখানোর জন্য ন্যূনতম ইউজার সংখ্যা বের করতে হবে। (একটা কথা মনে রাখতে হবে যে বন্ধুত্ব ট্রানজিটিভ নয়, অর্থাৎ x, y-এর বন্ধু এবং y, z-এর বন্ধু হলে এটার মানে x, z-এর বন্ধু নয়)।

উদাহরণস্বরূপ, ইনপুট n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] হলে আউটপুট হবে 2 কারণ আমাদের ভাষা ৩ ইউজার ১ এবং ৩-কে শিখাতে হবে, যেহেতু ২ জন ইউজার শেখাতে হবে তাই আউটপুট ২।

সমাধানের ধাপসমূহ

• lang := ইউজাররা যেসব ভাষা জানে সেটি ধারণকারী লিস্ট

• not_comm := একটি নতুন সেট

• friendships-এর প্রতিটি জোড়া a, b এর জন্য:

  • a := a - 1, b := b - 1

  • যদি lang[a] এবং lang[b] ডিসজয়েন্ট হয়, তবে:

    • a-কে not_comm-এ যোগ করুন

    • b-কে not_comm-এ যোগ করুন

• যদি not_comm খালি হয়, তবে 0 রিটার্ন করুন

• cnt := একটি খালি ম্যাপ

• not_comm-এর প্রতিটি person এর জন্য:

  • lang[person]-এর ফ্রিকোয়েন্সি cnt-এ সংরক্ষণ করুন

• temp := cnt-এর সব ভ্যালুর সর্বাধিক

• len(not_comm) - temp রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

from collections import Counter
def solve(n, languages, friendships):
    lang = [set(L) for L in languages]
    not_comm = set()
    for a, b in friendships:
        a -= 1
        b -= 1
        if lang[a].isdisjoint(lang[b]):
            not_comm.add(a)
            not_comm.add(b)
    if not not_comm:
        return 0
    cnt = Counter()
    for person in not_comm:
        cnt.update(lang[person])
    temp = max(cnt.values())
    return len(not_comm) - temp

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]
print(solve(n, languages, friendships))

ইনপুট

3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]

আউটপুট

2