मान लीजिए हमारे पास एक फ्रेंड्स लिस्ट है, जहां friends[i] उन लोगों की सूची है जिनसे i दोस्त है। दोस्ती का कनेक्शन दो-तरफा है। और प्रत्येक व्यक्ति खुद से दोस्त है, और दो लोग एक फ्रेंड ग्रुप में हैं जब तक कि उनके बीच आपसी दोस्तों का कोई पथ मौजूद है। हमें फ्रेंड ग्रुप की कुल संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]], तो आउटपुट 3 होगा, क्योंकि तीन फ्रेंड ग्रुप नीचे दिए गए हैं:

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- nodes := friends का आकार
- visited := nodes के समान आकार की एक सूची, जिसे False से भरा गया है
- ans := 0
- एक फ़ंक्शन dfs() परिभाषित करें। यह vertex, visited लेगा
- visited[vertex] := True
- friends[vertex] में प्रत्येक nei के लिए, करें
- यदि visited[nei] false है, तो
- dfs(nei, visited)
- यदि visited[nei] false है, तो
- मुख्य विधि से, निम्न करें:
- i को 0 से nodes तक रेंज में, करें
- यदि visited[i] false है, तो
- dfs(i, visited)
- ans := ans + 1
- यदि visited[i] false है, तो
- i को 0 से nodes तक रेंज में, करें
- 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))
इनपुट
[[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0] ]
आउटपुट
3