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

সমস্যা বিবরণ

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

উদাহরণ

ইনপুট: friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]]

আউটপুট: 3

কারণ তিনটি বন্ধু গোষ্ঠী হলো:

• গোষ্ঠী ১: ০, ১, ৫
• গোষ্ঠী ২: ২
• গোষ্ঠী ৩: ৩, ৪

সমাধানের পদ্ধতি

এই সমস্যাটি গ্রাফ থিওরির সংযুক্ত উপাদান (Connected Components) খুঁজে বের করার সমস্যা। আমরা ডিপথ-ফার্স্ট সার্চ (DFS) ব্যবহার করে সমাধান করব।

অ্যালগরিদম

1. nodes = বন্ধু তালিকার আকার
2. visited = nodes আকারের একটি বুলিয়ান অ্যারে, প্রাথমিকভাবে সব False
3. ans = ০ (গোষ্ঠীর সংখ্যা)
4. একটি dfs(vertex, visited) ফাংশন সংজ্ঞায়িত করুন:
   • visited[vertex] = True সেট করুন
   • friends[vertex] তালিকার প্রতিটি প্রতিবেশী nei এর জন্য:
     • যদি visited[nei] false হয়, তবে dfs(nei, visited) কল করুন
5. মূল ফাংশনে:
   • ০ থেকে nodes-1 পর্যন্ত লুপ চালান
   • যদি visited[i] false হয়, তবে:
     • dfs(i, visited) কল করুন
     • ans ১ বাড়ান
6. ans রিটার্ন করুন

পাইথন কোড

class Solution:
    def solve(self, friends):
        nodes = len(friends)
        visited = [False for _ in range(nodes)]
        ans = 0
        
        def dfs(vertex, visited):
            visited[vertex] = True
            for nei in friends[vertex]:
                if not visited[nei]:
                    dfs(nei, visited)
        
        for i in range(nodes):
            if not visited[i]:
                dfs(i, visited)
                ans += 1
        
        return ans

ob = Solution()
friends = [[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]]
print(ob.solve(friends))  # আউটপুট: 3

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(V + E) — যেখানে V হলো নোডের সংখ্যা এবং E হলো এজের সংখ্যা
• স্থান জটিলতা: O(V) — ভিজিটেড অ্যারে এবং রিকার্শন স্ট্যাকের জন্য

মূল বিষয়বস্তু

• DFS ব্যবহার করে গ্রাফে সংযুক্ত উপাদান গণনা করা হয়
• প্রতিটি অনদেখা নোড থেকে DFS চালু করলে একটি নতুন গোষ্ঠী मिलে
• এই প্যাটার্ন 소শ্যাল নেটওয়ার্ক অ্যানালাইসিস, নেটওয়ার্ক টপোলজি ইত্যাদিতে প্রয়োগ করা হয়