문제풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs(g, s, visited):             # g: 그래프 / s: 시작 정점 / visited: 방문 리스트
    result = 0                      # 감염 컴퓨터 수 셀 변수

    q = deque()                     # 큐 선언
    visited[s] = True               # 시작 정점 방문 처리
    q.append(s)                     # 큐에 삽입

    while q:                        # 큐 빌때까지
        v = q.popleft()             # 큐에서 하나 가져와서
        for u in g[v]:              # 인접 정점 다 돌면서
            if not visited[u]:      # 방문 안한 정점이면
                visited[u] = True   # 방문 처리
                q.append(u)         # 큐 삽입
                result += 1         # 감염 컴퓨터 +1
    return result                   # 결과 반환

n = int(input())                    # 컴퓨터 수
g = [[] for i in range(n + 1)]      # 그래프 담을 리스트, 인덱스 맞추려고 +1
visited = [False] * (n + 1)         # 방문 리스트

for i in range(int(input())):       # 인접 리스트 방식으로 기록
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

print(bfs(g, 1, visited))           # bfs 결과 출력

def solution(n, computers):
    answer = 0
    visited = [False] * n
    adjList = [[] for _ in range(n)]

    # 인접 리스트로 변환 (인접 행렬로 어떻게 풀어야 할지 감이 안오네..)
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                adjList[i].append(j)
    print(adjList)

    for i in adjList:
        for j in i:
            if not visited[j]:              # 모든 접점 방문 했는지 검사하면서 dfs 실행
                dfs(adjList, j, visited)
                answer += 1                 # dfs에서 인접 노드들은 모드 방문해 한 트리가 형성됨 고로 +1
    return answer

def dfs(g, v, visited):                     # dfs 실행 함수
    visited[v] = True                       # 방문 처리
    for i in g[v]:                          # 인접 노드들에 대해
        if not visited[i]:                  # 방문 안했으면
            dfs(g, i, visited)              # 그 노드에 대해 다시 dfs

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # 테스트용 코드