পাইথনে সম্ভাব্য দীর্ঘতম লাঠির দৈর্ঘ্য খুঁজতে প্রোগ্রাম?

ধরুন আমাদের কাছে পূর্ণসংখ্যার স্টিকের একটি তালিকা আছে। এখানে তালিকার প্রতিটি উপাদান দুটি প্রান্তের সাথে একটি লাঠির প্রতিনিধিত্ব করে, এই মানগুলি 1 থেকে 6 এর মধ্যে। এগুলি প্রতিটি প্রান্তকে প্রতিনিধিত্ব করছে। আমরা দুটি লাঠি একসাথে সংযুক্ত করতে পারি যদি তাদের কোন প্রান্ত একই হয়। ফলস্বরূপ লাঠির শেষ হবে অবশিষ্ট প্রান্ত এবং এর দৈর্ঘ্য বৃদ্ধি করা হয়। আমাদের সম্ভাব্য দীর্ঘতম লাঠির দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি লাঠির মত হয় =[ [2, 3], [2, 4], [3, 5], [6, 6]], তাহলে আউটপুট হবে 3, যেমন আমরা সংযোগ করতে পারি [2, 3] ] এবং [2, 4] পেতে [3, 4], যা আমরা [4, 5] পেতে [3, 5] এর সাথে সংযোগ করতে পারি।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড, edge_idx এবং পরিদর্শন করা একটি সেট গ্রহণ করবে

• যদি edge_idx শূন্য না হয়, তাহলে

  • যদি edge_idx পরিদর্শন করা হয়, তাহলে

    • রিটার্ন 0

  • edge_idx কে পরিদর্শন করা হিসাবে চিহ্নিত করুন

  • res :=0

  • g[নোড]-এ প্রতিটি e_idx-এর জন্য করুন

    • n_node :=স্টিকস[e_idx, 0] যখন স্টিক হয়[e_idx, 1] নোডের মতই হয় অন্যথায় লাঠি হয়[e_idx, 1]

    • res :=সর্বাধিক res এবং 1 + dfs(n_node, e_idx, পরিদর্শন করা)

  • যদি edge_idx অ-শূন্য হয়, তাহলে

    • পরিদর্শন করা থেকে edge_idx মুছুন

  • রিটার্ন রিটার্ন

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

• লাঠি :=লাঠিতে থাকা সকলের জন্য একটি তালিকা (s[0], s[1])

• শীর্ষবিন্দু :=একটি নতুন সেট

• g :=একটি খালি মানচিত্র

• প্রতিটি সূচী i এবং কাঠিতে প্রান্তের জন্য, করুন

  • g[edge[0]]

    -এ i ঢোকান

  • g[edge[1]]

    -এ i ঢোকান

  • প্রান্ত [0] এবং প্রান্ত [1] শীর্ষবিন্দুতে প্রবেশ করান

• res :=0

• প্রতিটি v এর জন্য শীর্ষবিন্দুতে, করুন

  • res :=res এবং dfs এর সর্বাধিক (v, নাল, এবং খালি সেট)

• রিটার্ন রেস - 1

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

উদাহরণ

from collections import defaultdict

class Solution:
   def solve(self, sticks):
      def dfs(node, edge_idx, visited):
         if edge_idx is not None:
            if edge_idx in visited:
               return 0
            visited.add(edge_idx)
         res = 0
         for e_idx in g[node]:
            n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
            res = max(res, 1 + dfs(n_node, e_idx, visited))
         if edge_idx:
            visited.remove(edge_idx)
         return res

      sticks = [(s[0], s[1]) for s in sticks]
      vertices = set()
      g = defaultdict(set)
      for i, edge in enumerate(sticks):
         g[edge[0]].add(i)
         g[edge[1]].add(i)
         vertices.add(edge[0])
         vertices.add(edge[1])
      res = 0
      for v in vertices:
         res = max(res, dfs(v, None, set()))
      return res - 1

ob = Solution()
sticks = [
   [2, 3],
   [2, 4],
   [3, 5],
   [6, 6]
]
print(ob.solve(sticks))

ইনপুট

sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]

আউটপুট

3