가오리의 코딩일기

[11724] 연결 요소의 개수 본문

Python/백준

[11724] 연결 요소의 개수

류경혜 2022. 8. 21. 18:30

import sys
from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start] = True 
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    
n,m = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1)]

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False] *(n+1)
result =0 

for i in range(1, n+1):
    if not visited[i]:
        if not graph[i]:
            result += 1 
            visited[i] = True 
        else:
            bfs(i)
            result += 1 
print(result)

'Python > 백준' 카테고리의 다른 글

[2667] 단지번호 붙이기  (0) 2022.08.21
[10451] 순열 사이클  (0) 2022.08.21
[1406] 에디터  (0) 2022.08.15
[1158] 요세푸스 문제  (0) 2022.08.15
[1850] 최대공약수  (0) 2022.08.15