पायथन में दुखी मित्रों की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास n (सम) विभिन्न मित्रों के लिए प्राथमिकताओं की एक सूची है। प्रत्येक व्यक्ति i के लिए, वरीयताएँ [i] वरीयता क्रम में क्रमबद्ध मित्रों की एक सूची रखती है। तो, सूची में पहले वाले मित्र को बाद में सूची में मित्र की तुलना में अधिक पसंद किया जाता है। प्रत्येक सूची में मित्रों को 0 से n-1 तक पूर्णांकों द्वारा क्रमांकित किया जाता है। सभी दोस्तों को अलग-अलग जोड़ियों में बांटा गया है। जहां जोड़े [i] =[xi, yi] xi को yi के साथ जोड़ा जाता है और/या yi को xi के साथ जोड़ा जाता है। लेकिन एक मित्र x दुखी होता है यदि x को y के साथ जोड़ा जाता है और एक मित्र u मौजूद होता है जिसे v के साथ भी जोड़ा जाता है लेकिन -

• x आपको y से अधिक पसंद करता है, और
• आप वी से अधिक एक्स पसंद करते हैं।

हमें दुखी मित्रों की संख्या ज्ञात करनी है।

इसलिए, यदि इनपुट पसंद की तरह है =[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] जोड़े =[[0, 1] , [2, 3]], तो आउटपुट 2 होगा क्योंकि पहला दोस्त नाखुश है क्योंकि व्यक्ति 1 को व्यक्ति 0 के साथ जोड़ा जाता है, लेकिन व्यक्ति 3 को व्यक्ति 0 से अधिक पसंद करता है, और व्यक्ति 3 व्यक्ति 2 को पसंद करता है। और दोस्त 3 दुखी है। क्योंकि व्यक्ति 3 को व्यक्ति 2 के साथ जोड़ा जाता है लेकिन व्यक्ति 1 को व्यक्ति 2 से अधिक पसंद किया जाता है, और व्यक्ति 1 व्यक्ति 3 को व्यक्ति 0 से अधिक पसंद करता है।

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

• ग्राफ:=ग्राफ बनाने के लिए एक आसन्न सूची, शुरू में खाली
• जोड़ों में प्रत्येक जोड़ी (एस, ई) के लिए, करें
  • प्राथमिकताओं में प्रत्येक वरीयता के लिए[s], करें
    • यदि वरीयता अंत के समान है, तो
      • लूप से बाहर आएं
    • ग्राफ[s, pref] :=1
  • प्राथमिकताओं में प्रत्येक वरीयता के लिए[e], करें
    • यदि प्रीफ़ प्रारंभ के समान है, तो
      • लूप से बाहर आएं
    • ग्राफ[ई, प्रीफ] :=1
• दुखी :=0
• जोड़ों में प्रत्येक जोड़ी (एस, ई) के लिए, करें
  • ग्राफ़ में प्रत्येक प्रीफ़ के लिए[s], करें
    • अगर ग्राफ़[pref][s] खाली नहीं है, तो
      • दुखी:=दुखी + 1
      • लूप से बाहर आएं
  • ग्राफ़ में प्रत्येक प्रीफ़ के लिए[अंत], करें
    • अगर ग्राफ़[pref][e] खाली नहीं है, तो
      • दुखी:=दुखी + 1
      • लूप से बाहर आएं
• दुखी होकर लौटना

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import defaultdict
def solve(preferences, pairs):
   graph = defaultdict(dict)
   for start, end in pairs:
      for pref in preferences[start]:
         if pref == end:
            break
         graph[start][pref] = 1
      for pref in preferences[end]:
         if pref == start:
            break
         graph[end][pref] = 1

   unhappy = 0

   for start, end in pairs:
      for pref in graph[start]:
         if graph[pref].get(start, None):
            unhappy += 1
            break
      for pref in graph[end]:
         if graph[pref].get(end, None):
            unhappy += 1
            break
   return unhappy

preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]
pairs = [[0, 1], [2, 3]]
print(solve(preferences, pairs))

इनपुट

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]

आउटपुट

2