boj 11724 연결 요소의 개수 (실버2)

boj 11724 연결 요소의 개수

인풋값으로 주어지는 두 점을 연결하는 그래프를 만들어준다.
각각의 점을 노드로 삼고 각 점에서 그어진 선을 모두 배열로 넣어주기위해
a,b가 이어진다면 a.append(b), b.append(a) 이렇게 2가지 처리를 해준다.

모든 그래프 상태에 대한 입력이 끝났으면, dfs로 맨 첫 노드부터 시작해서 탐색을 시작한다.
연결된 선으로 갈수있는 모든 곳을 다 탐색했으면 종료하고, 아직 탐색되지 않은곳을 다음 시작점으로 삼고
count를 1 올려준다.
최종적으로 탐색이 끝났을때 count값을 체크해서 몇덩이인지 출력한다.

내 풀이

import sys
from collections import deque
sys.setrecursionlimit(10000)

n,m = map(int,input().split())
graph = [[] for i in range(n+1)]

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
  
visited = [False] * (n+1)
count = 0

def dfs(a):
  visited[a] = True
  q = graph[a]
  while(q):
    next = q.pop()
    if visited[next] == False:
      dfs(next)

for i in range(1,n+1):
  if visited[i] == False:
    count += 1
    dfs(i)

print(count)

회고

시간복잡도 상으로는 분명 충분히 될것같은데 자꾸 2번째 테스트케이스에서 시간초과가 나서 pypy로 돌려보았더니 잘된다. ㅠㅠ 왜안될까..

결과