LeetCode : Number of Connected Components in an Undirected Graph

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

連結グラフの数を数える問題

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        def add_to_connected(one,another,connected):
            if one in connected:
                connected[one].add(another)
            else:
                connected[one] = set([another])
                
        connected = {}
        for left, right in edges:
            add_to_connected(left,right,connected)
            add_to_connected(right,left,connected)
            
        checked = [0 for _ in range(n)]
        
        def dfs(connected, node):
            if checked[node] == 1:
                return True
            checked[node] = 1
            
            # 接続先が無ければ何もしない
            if not node in connected:
                return True
            
            for next_node in connected[node]:
                _ = dfs(connected, next_node)
               
            return True
        cnt = 0
        for i in range(n):
            if checked[i] == 0:
                cnt += 1
                _ = dfs(connected, i)
        
        return cnt