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

ধরুন আমাদের কাছে 1 থেকে n লেবেলযুক্ত n নোড সহ একটি অনির্দেশিত তারকা গ্রাফ রয়েছে। আমরা জানি একটি স্টার গ্রাফ হল এমন একটি গ্রাফ যেখানে একটি কেন্দ্র নোড এবং ঠিক n - 1টি প্রান্ত রয়েছে যা প্রতিটি অন্য নোডের সাথে কেন্দ্রের নোডকে সংযুক্ত করে। আমাদের প্রদত্ত তারার গ্রাফের কেন্দ্র খুঁজে বের করতে হবে।

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

তাহলে আউটপুট 3 হবে কারণ 3 কেন্দ্রে রয়েছে।

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

দেখা হয়েছে :=একটি নতুন সেট
গ্রাফে প্রতিটি প্রান্তের (u,v) জন্য, করুন
- যদি আপনি দেখতে পান, তাহলে
  - ফেরত দিন
- যদি v দেখা যায়, তাহলে
  - প্রত্যাবর্তন v
- আপনাকে দেখাতে ঢোকান
- ভি সন্নিবেশ করান

উদাহরণ

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

def solve(graph):
   seen = set()

   for u,v in graph:
      if u in seen:
         return u
      if v in seen:
         return v
      seen.add(u)
      seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

ইনপুট

[(1,3),(2,3),(4,3),(5,3),(6,3)]