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

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

ตัวอย่างเช่น หากอินพุตคือ friends = [[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]] ผลลัพธ์จะเป็น 3 เนื่องจากมีกลุ่มเพื่อน 3 กลุ่ม ดังนี้:

• กลุ่มที่ 1: 0, 1, 5
• กลุ่มที่ 2: 2
• กลุ่มที่ 3: 3, 4

แนวทางแก้ปัญหา

1. กำหนด nodes = ขนาดของรายชื่อเพื่อน
2. สร้างรายการ visited ขนาดเท่า nodes เติมด้วย False
3. กำหนด ans = 0
4. สร้างฟังก์ชัน dfs(vertex, visited):
   • ตั้ง visited[vertex] = True
   • วนลูปผ่านเพื่อนบ้านแต่ละคนใน friends[vertex]:
     • หาก visited[nei] เป็น False ให้เรียก dfs(nei, visited) แบบเรียกซ้ำ
5. ในโปรแกรมหลัก วนลูป i จาก 0 ถึง nodes-1:
   • หาก visited[i] เป็น False:
     • เรียก dfs(i, visited)
     • เพิ่ม ans ขึ้น 1
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))  # Output: 3

อินพุต

[[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]]

เอาต์พุต

3