โปรแกรมหาจำนวนกลุ่มเพื่อนในชุดการเชื่อมต่อเพื่อนใน Python

สมมติว่าเรามีรายชื่อเพื่อน โดยที่ friends[i] คือรายชื่อบุคคลที่ฉันเป็นเพื่อนด้วย ความผูกพันธ์เป็นสองทาง และแต่ละคนเป็นเพื่อนกับตัวเองและสองคนอยู่ในกลุ่มเพื่อนตราบเท่าที่มีเส้นทางของเพื่อนร่วมทางที่เชื่อมโยงกัน เราต้องหาจำนวนกลุ่มเพื่อนทั้งหมด

ดังนั้น ถ้าอินพุตเหมือนเพื่อน =[[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]] แล้วผลลัพธ์ จะเป็น 3 เนื่องจากกลุ่มเพื่อนทั้งสามมีดังต่อไปนี้ -

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• โหนด :=ขนาดของเพื่อน
• เข้าชมแล้ว :=รายการขนาดเท่ากับโหนดและเติมเท็จ
• ตอบ :=0
• กำหนดฟังก์ชัน dfs() นี่จะเป็นจุดยอด เยี่ยมชม
• เยี่ยมชมแล้ว[จุดยอด] :=จริง
• สำหรับแต่ละ nei ในเพื่อน[vertex] ทำ
  • ถ้ามาเยี่ยม[nei] เป็นเท็จ แล้ว
    • dfs(nei, เยี่ยมชม)
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• สำหรับ i ในช่วง 0 ถึงโหนด ทำ
  • ถ้ามาเยี่ยม[i] จะเป็นเท็จ
    • dfs(i, เยี่ยมชม)
    • อัน :=ans + 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