পাইথনে বন্ধুর সংযোগের একটি সেটে বন্ধু গোষ্ঠীর সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বন্ধুর তালিকা আছে, যেখানে বন্ধু[i] হল আমি যাদের সাথে বন্ধুত্ব করি তাদের একটি তালিকা৷ বন্ধুত্বের সংযোগ দ্বিমুখী। এবং প্রতিটি ব্যক্তি নিজেদের সাথে বন্ধু এবং দুই ব্যক্তি একটি বন্ধু গোষ্ঠীতে থাকে যতক্ষণ না পারস্পরিক বন্ধুদের সংযোগ করার কিছু পথ থাকে। আমাদের মোট বন্ধু দলের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট বন্ধুদের মত হয় =[[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]], তাহলে আউটপুট 3 হবে, যেহেতু তিনটি বন্ধু গ্রুপ নিচের মত −

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

• নোডস :=বন্ধুদের আকার
• ভিজিট করা হয়েছে :=নোডের মতো আকারের একটি তালিকা এবং False দিয়ে পূরণ করুন
• উত্তর :=0
• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি শীর্ষবিন্দু লাগবে, পরিদর্শন করা হয়েছে
• ভিজিট করা হয়েছে[vertex] :=সত্য
• বন্ধুদের মধ্যে প্রতিটি nei এর জন্য[vertex], করুন
  • যদি পরিদর্শন করা হয়[nei] মিথ্যা, তাহলে
    • dfs(nei, পরিদর্শন করা)
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• আমি 0 থেকে নোডের রেঞ্জের জন্য, কর
  • যদি পরিদর্শন করা হয়[i] মিথ্যা হয়, তাহলে
    • dfs(i, পরিদর্শন করা হয়েছে)
    • উত্তর :=উত্তর + ১
• উত্তর ফেরত দিন

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

উদাহরণ

শ্রেণির সমাধান:def solve(self, friends):nodes =len(friends) visited =[False for _ in range(nodes)] ans =0 def dfs(vertex, visited):visited[vertex] =এর জন্য সত্য বন্ধুদের মধ্যে nei [ভার্টেক্স]:যদি পরিদর্শন না করা হয় [nei]:dfs(nei, পরিদর্শন করা) i এর জন্য রেঞ্জে (নোড):যদি পরিদর্শন না করা হয় [i]:dfs(i, পরিদর্শন করা) উত্তর +=1 রিটার্ন ansob =সমাধান( )বন্ধু =[ [0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0] ]প্রিন্ট(ob.solve(বন্ধুদের)) 
ইনপুট
 
[[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]]
 
আউটপুট
 
3