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

아... 처음에 이 코드로 풀었는데 시간초과가 떳다..

 

from collections import deque

def BFS():
    counter = 0
    nodes =  list(range(1, N + 1))
    visited = []
    que = deque()
    while len(nodes) != 0:
        que.append(nodes[0])
        while que:
            node = que.popleft()
            if node in visited:
                continue
            nodes.remove(node)
            if node not in visited:
                visited.append(node)
                que.extend(sorted(graph[node]))
        counter += 1
    return counter


N, M = map(int, input().split())
graph = [set([]) for i in range(N + 1)]

for _ in range(M):
    V1, V2 = map(int, input().split())
    graph[V1].add(V2)
    graph[V2].add(V1)

print(BFS())

 

그래서 나름 해본다고 하다가..

 

잘 안되길래 다른 사람 답안을 봤는데

 

약간 예상했었던 숫자가 아닌 index로 푸는 방식 + DFS + 재귀

 

아직은 식견이 좁지 않나 라는 생각을 했다..

 

재귀 쓰니까 정말 간단하게 풀렸다..

 

아 그리고 입력받을때 

 

N, M = map(int, sys.stdin.readline().split())

이렇게 해야된다.. 

 

안그러면... 시간초과 뜸.. 

 

import sys
sys.setrecursionlimit(10000000)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

def DFS(i):
    visited[i] = True
    for ni in graph[i]:
        if visited[ni] is False:
            DFS(ni)

for _ in range(M):
    V1, V2 = map(int, sys.stdin.readline().split())
    graph[V1].append(V2)
    graph[V2].append(V1)

counter = 0

for i in range(1, N + 1):
    if visited[i] is False:
        DFS(i)
        counter += 1

print(counter)