[백준] 11724 파이썬(python) : 연결 요소의 개수 - (★)

11724번: 연결 요소의 개수

 

 

import sys
n, m = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
cnt = 0
visit = [False] * (n+1)

def dfs(v):
    visit[v] = True
    for i in graph[v]:
        if not visit[i]:
            dfs(i)

for i in range(1, n+1):
    if not visit[i]:
        dfs(i)
        cnt += 1
print(cnt)

 

2606번 : 바이러스문제와 비슷한 문제였다. 개인적으로 연결된 노드 끼리의 팀 숫자를 구하는 문제에서 다른 문제도 생각났는데 문제번호가 기억이 안난다.

 

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0] * (n+1)
cnt = 0
def bfs(v):
    q = deque()
    q.append(v)
    visited[v] = 1
    while q:
        now = q.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                visited[i] = 1
                q.append(i)
for i in range(1, n+1):
    if visited[i] == 0:
        bfs(i)
        cnt += 1
print(cnt)