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

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

हल करने के चरण

1. lang := उपयोगकर्ताओं द्वारा जानी जाने वाली भाषाओं के सभी विशिष्ट सेट की सूची
2. not_comm := एक नया सेट
3. friendships में प्रत्येक जोड़ी a, b के लिए:
   • a := a - 1
   • b := b - 1
   • यदि lang[a] और lang[b] डिसजॉइंट हैं, तो:
     • a को not_comm में डालें
     • b को not_comm में डालें
4. यदि not_comm खाली है, तो 0 वापस करें।
5. cnt := एक खाली मैप
6. not_comm में प्रत्येक person के लिए:
   • lang[person] की फ्रीक्वेंसी स्टोर करें और cnt में स्टोर करें
7. temp := cnt के सभी मानों की सूची का अधिकतम
8. 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