पायथन में पढ़ाने के लिए न्यूनतम संख्या में लोगों को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या n है, एक सरणी जिसे 'भाषाएँ' कहा जाता है, और एक सरणी जिसे 'मैत्री' कहा जाता है, इसलिए n भाषाएँ 1 से 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 होगा क्योंकि हमें भाषा 3 को उपयोगकर्ताओं 1 और 3 को प्रशिक्षित करने की आवश्यकता है, क्योंकि सिखाने के लिए दो उपयोगकर्ता हैं, इसलिए आउटपुट 2 है।

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

• lang :=उपयोगकर्ताओं द्वारा ज्ञात सभी विशिष्ट भाषाओं की सूची
• not_comm :=एक नया सेट
• दोस्ती में प्रत्येक जोड़ी के लिए ए, बी, करते हैं
  • a :=a - 1
  • b :=b - 1
  • यदि lang[a] और lang[b] संयुक्त हैं, तो
    • not_comm में एक डालें
    • not_comm में b डालें
• अगर not_comm खाली है, तो
  • वापसी 0
• cnt :=एक खाली नक्शा
• not_comm में प्रत्येक व्यक्ति के लिए, करें
  • लैंग की आवृत्ति [व्यक्ति] स्टोर करें और इसे सीएनटी में स्टोर करें
• अस्थायी:=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