[Algorithm] Graph Number

from collections import defaultdict

def bfs(g, start):
    global cnt
    qu = []          # 기억 장소 1: 앞으로 처리해야 할 꼭짓점을 큐에 저장
    done = set()     # 기억 장소 2: 이미 큐에 추가한 꼭짓점들을 집합에 기록(중복 방지)
 
    for j in g:
        if j not in done:
            qu.append(j) # 시작점을 큐에 넣고 시작
            done.add(j)  # 집합에도 추가
            cnt += 1
            while qu:                 # 큐에 처리할 꼭짓점이 남아 있으면
                p = qu.pop(0)         # 큐에서 처리 대상을 꺼내어
                print(p)              # 꼭짓점 이름을 출력하고
                for x in g[p]:        # 대상 꼭짓점에 연결된 꼭짓점들 중에
                    if x not in done: # 아직 큐에 추가된 적이 없는 꼭짓점들을
                        qu.append(x)  # 큐에 추가하고
                        done.add(x)   # 집합에도 추가
        print(done)
cnt = 0
g = defaultdict(lambda: [])
a = [
    [1,3],
    [3,4]
]

for x,y in a:
    g[x].append(y)
    g[y].append(x)
    
print(g)
bfs(g, 1)
print(cnt)