ধরুন আমাদের একটি সংখ্যা n আছে, 'ভাষা' নামক একটি অ্যারে এবং 'বন্ধুত্ব' নামক একটি অ্যারে, তাই 1 থেকে n পর্যন্ত n ভাষা রয়েছে, ভাষা[i] ব্যবহারকারীর জানা ভাষার একটি সেট প্রতিনিধিত্ব করে এবং বন্ধুত্ব[ i] একটি জোড়া ধারণ করে [ui, vi] ব্যবহারকারী ui এবং vi-এর মধ্যে বন্ধুত্বকে বোঝায়। আমরা একটি ভাষা নির্বাচন করতে পারি এবং কিছু ব্যবহারকারীকে তা শেখাতে পারি যাতে সমস্ত বন্ধু একে অপরের সাথে যোগাযোগ করতে পারে। আমাদের শেখানোর জন্য প্রয়োজনীয় ব্যবহারকারীদের ন্যূনতম সংখ্যা খুঁজে বের করতে হবে। (একটি জিনিস আমাদের মনে রাখতে হবে যে বন্ধুত্ব ট্রানজিটিভ নয়, তাই x যদি y এর বন্ধু হয় এবং y z এর বন্ধু হয় তবে এর অর্থ এই নয় যে x z এর বন্ধু)।
সুতরাং, যদি ইনপুট হয় n =3 ভাষা =[[2],[1,3],[1,2],[3]] বন্ধুত্ব =[[1,4],[1,2],[3 ,4],[2,3]], তাহলে আউটপুট 2 হবে কারণ আমাদের 1 এবং 3 ব্যবহারকারীদের ভাষা 3 প্রশিক্ষণ দিতে হবে, যেহেতু শেখানোর জন্য দুটি ব্যবহারকারী আছে, তাই আউটপুট 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- lang :=ব্যবহারকারীদের দ্বারা পরিচিত সমস্ত স্বতন্ত্র ভাষার সেটের একটি তালিকা
- not_comm :=একটি নতুন সেট
- প্রতিটি জোড়ার জন্য a, b বন্ধুত্বে, do
- a :=a - 1
- b :=b - 1
- যদি lang[a] এবং lang[b] বিচ্ছিন্ন হয়, তাহলে
- not_comm এ ঢোকান
- not_comm-এ b ঢোকান
- যদি not_comm খালি হয়, তাহলে
- রিটার্ন 0
- cnt :=একটি খালি মানচিত্র
- not_comm-এ প্রতিটি ব্যক্তির জন্য, করুন
- lang[person] এর ফ্রিকোয়েন্সি সংরক্ষণ করুন এবং এটিকে cnt এ সংরক্ষণ করুন
- temp :=cnt-এর সমস্ত মানের তালিকার সর্বোচ্চ
- 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
