ব্যক্তিদের আলাদা করার প্রোগ্রাম যেখানে পাইথনে কোনো শত্রু একই গ্রুপে থাকতে পারবে না

ধরুন আমাদের একটি সংখ্যা n এবং একটি 2D ম্যাট্রিক্স আছে যাকে শত্রু বলা হয়। এখানে n নির্দেশ করে যে [0, n - 1] থেকে npeople লেবেল করা আছে। এখন শত্রুদের প্রতিটি সারিতে রয়েছে [a, b] যার মানে a এবং b শত্রু। আমাদের পরীক্ষা করতে হবে যে এন লোকেদের দুটি দলে বিভক্ত করা সম্ভব কি না যাতে কোনও দু'জন শত্রু যারা একই দলে না থাকে।

সুতরাং, যদি ইনপুটটি n =4, enemies =[[0, 3],[3, 2]] এর মত হয়, তাহলে আউটপুট হবে True, কারণ আমাদের এই দুটি গ্রুপ থাকতে পারে [0, 1, 2] এবং [ 3]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• গ্রাফ :=একটি খালি সংলগ্ন তালিকা

• শত্রুদের মধ্যে প্রতিটি শত্রু জোড়া (u, v) এর জন্য, করুন

  • গ্রাফ[u]

    -এর শেষে v সন্নিবেশ করান

  • গ্রাফের শেষে u ঢোকান[v]

• রঙ :=একটি নতুন মানচিত্র

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি u, c :=0 শুরুতে লাগবে

• আপনি যদি রঙিন হন, তাহলে

  • যখন [u] রঙ c

    এর মত একই হয় তখন true ফেরত দিন

• রঙ[u] :=c

• গ্রাফ[u]-এ প্রতিটি v-এর জন্য সমস্ত dfs(v, c XOR 1) সত্য হলে ফিরে আসে

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• 0 থেকে n রেঞ্জের প্রতিটি u এর জন্য সমস্ত (dfs(u) এবং যদি আপনি রঙে না থাকে) সত্য হয়

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, n, enemies):
      from collections import defaultdict
      graph = defaultdict(list)
      for u, v in enemies:
         graph[u].append(v)
         graph[v].append(u)
      color = {}
      def dfs(u, c=0):
         if u in color:
            return color[u] == c
            color[u] = c
            return all(dfs(v, c ^ 1) for v in graph[u])
         return all(dfs(u) for u in range(n) if u not in color)
ob = Solution()
n = 4
enemies = [[0, 3],[3, 2]]
print(ob.solve(n, enemies))

ইনপুট

4, [[0, 3],[3, 2]]

আউটপুট

True