백준 11724 python [연결 요소의 개수]

https://www.acmicpc.net/problem/11724

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
list = [[] for i in range(N+1)]
visited = [False] * (N+1)
cnt = 0

for i in range(M):
    a, b = map(int, input().split())
    list[a].append(b)
    list[b].append(a)


def bfs(k):
    Q = deque([k])
    visited[k] = True
    
    while Q:
        a = Q.popleft()

        for i in list[a]:
            if(visited[i] == False):
                visited[i] = True
                Q.append(i)

for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        cnt += 1

print(cnt)

---

이번 문제를 풀면서
input() 대신 sys.stdin.readline을 사용해야 한다는걸 알았다.

input()을 쓰면 파라미터 타입에 맞게 일일이 형변환시켜주기 때문에
시간초과가 난다고 한다.

그리고 처음에는 아래 코드부분에서 cnt를 +1 해줬는데
틀렸다고 하는것이다.

if(visited[i] == False):
	visited[i] = True
	Q.append(i)

원인은 문제의 요구사항이 연결요소의 개수를 구하는 것이기 때문에
bfs 함수 호출 시에만 +1을 해줘야 한다.

아무튼 인접 리스트 방식으로 구현을 해서 해결해봤다.