<dfs/bfs> 백준 11724번. 연결 요소의 개수

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

11724번: 연결 요소의 개수

시험공부할 땐 공부빼곤 다 재밌는게 사이언스. . .

import sys
from collections import deque

input=sys.stdin.readline

n, m = map(int, input().split())
graph = [[]*(n+1) for i in range(n+1)];
visited = [False]*(n+1) #연결 개수를 세기 위한 visited
cnt = 0 #연결 개수

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b);
  graph[b].append(a);

def bfs(n, visited):
  q = deque()
  q.append(n)
  while q:
    nn = q.popleft()
    visited[nn] = True
    for i in graph[nn]:    
      if (visited[i] == False) : #방문하지 않은 노드라면
        visited[i] = True #방문처리를 해줌
        q.append(i)                  #큐에 넣어준다

for i in range(1, len(graph)):
  if (visited[i] == False): #방문하지 않은 노드라면
    cnt += 1
    bfs(i,visited)


print (cnt)

bfs로 풀어주었다. 시간초과가 나서 sys.stdin.realine을 추가해줬더니 통과하였다.

1번부터 n번 노드까지 bfs로 탐색하주는데, 방문하지 않은 노드는 제외하고 총 몇 번이 실행됐는지를 출력하면 연결 요소의 개수가 출력된다.

크게 어려운 문제는 아니였다.