पायथन में दोस्तों के कनेक्शन के एक सेट में मित्र समूहों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक मित्र सूची है, जहां मित्र [i] उन लोगों की सूची है जिनके साथ मैं मित्र हूं। दोस्ती का रिश्ता दोतरफा होता है। और प्रत्येक व्यक्ति अपने आप से मित्र है और दो व्यक्ति एक मित्र समूह में तब तक हैं जब तक परस्पर मित्रों को जोड़ने का कोई मार्ग है। हमें मित्र समूहों की कुल संख्या ज्ञात करनी है।

तो, अगर इनपुट दोस्तों की तरह है =[[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]], तो आउटपुट 3 होंगे, क्योंकि तीन मित्र समूह इस प्रकार हैं -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नोड्स :=दोस्तों का आकार
• देखा गया :=नोड्स के समान आकार की एक सूची और गलत से भरें
• उत्तर:=0
• एक फ़ंक्शन को परिभाषित करें dfs() । यह शीर्ष पर जाएगा, दौरा किया
• विज़िट किया[वर्टेक्स] :=सच
• दोस्तों में प्रत्येक नी के लिए[वर्टेक्स], करें
  • अगर विज़िट किया गया [नेई] गलत है, तो
    • dfs(nei, देखे गए)
• मुख्य विधि से, निम्न कार्य करें -
• मैं के लिए 0 से नोड्स की सीमा में, करते हैं
  • अगर विज़िट किया गया[i] गलत है, तो
    • dfs(i, देखे गए)
    • उत्तर:=उत्तर + 1
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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