পাইথনের প্রত্যেকের দ্বারা গ্রাফটি অতিক্রম করা যায় কিনা তা খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের একটি গ্রাফ দেওয়া হয়েছে যাতে 0 থেকে n - 1 পর্যন্ত n শীর্ষবিন্দু রয়েছে। গ্রাফটি অনির্দেশিত এবং প্রতিটি প্রান্তের একটি ওজন রয়েছে। গ্রাফটিতে তিন ধরনের ওজন থাকতে পারে এবং প্রতিটি ওজন একটি নির্দিষ্ট কাজকে নির্দেশ করে। জ্যাক এবং কেসি নামে দুটি লোক গ্রাফটি অতিক্রম করতে পারে। একটি প্রান্তের ওজন 1 থাকলে জ্যাক গ্রাফটি অতিক্রম করতে পারে, ক্যাসি গ্রাফটি অতিক্রম করতে পারে যদি এটির ওজন 2 থাকে এবং উভয়ই গ্রাফটি অতিক্রম করতে পারে যদি এটির প্রান্তের ওজন 3 থাকে। উভয়ের জন্য গ্রাফটিকে অতিক্রমযোগ্য করার জন্য আমাদের প্রয়োজনীয় যেকোনো প্রান্ত সরিয়ে ফেলতে হবে জ্যাক এবং কেসি। আমরা গ্রাফটিকে ট্র্যাভার্সেবল করতে অপসারণের জন্য প্রান্তের সংখ্যা ফেরত দিই, অথবা যদি এটিকে অতিক্রমযোগ্য না করা যায় তবে আমরা -1 ফেরত দিই।

সুতরাং, যদি ইনপুট মত হয়

এবং n =5; তাহলে আউটপুট হবে -1

একটি প্রান্ত অপসারণ করে গ্রাফটিকে উভয়ের জন্য অতিক্রমযোগ্য করা যাবে না। সুতরাং, উত্তর হল -1।

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

• একটি ফাংশন সংজ্ঞায়িত করুন find()। এটি ভাল লাগবে

  • যদি val root[val] এর মত না হয়, তাহলে

    • root[val] :=find(root[val])

  • রিটার্ন রুট[ভাল]

• একটি ফাংশন ইউনিয়ন () সংজ্ঞায়িত করুন। এটি val1, val2

  নেবে

  • val1:=find(val1)

  • val2 :=find(val2)

  • যদি val1 val2 এর মত হয়, তাহলে

    • রিটার্ন 0

  • root[val1] :=val2

  • রিটার্ন 1

• res :=0

• edge1 :=0

• edge2 :=0

• root :=পরিসর 0 থেকে n + 1

  পর্যন্ত একটি নতুন তালিকা

• প্রতিটি প্রান্তের জন্য (u, v), এবং এর ওজন w e, do

  • আপনি যদি 3 এর সমান হন, তাহলে

    • যদি ইউনিয়ন(v, w) অ-শূন্য হয়, তাহলে

      • edge1 :=edge1 + 1

      • edge2 :=edge2 + 1

    • অন্যথায়,

      • res :=res + 1

• root0 :=root[সূচী 0 থেকে শেষ]

• প্রতিটি প্রান্তের জন্য (u, v), এবং এর ওজন w e, do

  • আপনি যদি 1 এর মত হয়, তাহলে

    • যদি ইউনিয়ন(v, w) অ-শূন্য হয়, তাহলে

      • edge1 :=edge1 + 1

    • অন্যথায়,

      • res :=res + 1

• root :=root0

• প্রতিটি প্রান্তের জন্য (u, v), এবং এর ওজন w e, do

  • আপনি যদি 2 এর সমান হন, তাহলে

    • যদি ইউনিয়ন(v, w) অ-শূন্য হয়, তাহলে

      • edge2 :=edge2 + 1

    • অন্যথায়,

      • res :=res + 1

• edge1 যদি edge2 এবং n - 1

  এর মত হয় তাহলে res ফেরত দিন

• অন্যথায়, ফিরুন -1

উদাহরণ

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

def solve(n, e):
   def find(val):
      if val != root[val]:
         root[val] = find(root[val])
      return root[val]
   def union(val1, val2):
      val1, val2 = find(val1), find(val2)
      if val1 == val2: return 0
      root[val1] = val2
      return 1
   res = edge1 = edge2 = 0
   root = list(range(n + 1))
   for u, v, w in e:
      if u == 3:
         if union(v, w):
            edge1 += 1
            edge2 += 1
         else:
            res += 1
   root0 = root[:]
   for u, v, w in e:
      if u == 1:
         if union(v, w):
            edge1 += 1
      else:
            res += 1
   root = root0
   for u, v, w in e:
      if u == 2:
         if union(v, w):
            edge2 += 1
         else:
            res += 1
   return res if edge1 == edge2 == n - 1 else -1
print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))

ইনপুট

Input:
5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]

আউটপুট

-1