백준 11724 - 연결 요소

미방향 그래프 연결 요소 개수 구하기
N M 이 주어진다. 사이즈 작음

입력 예제로 따라가기

연결요소

connected component

한 노드에 대해서 BFS 돌 때마다 1번씩 카운트

graph[a].append(b) 꼴로 넣는 이유는 연결리스트로 나타내기 위함.
1-2,5
2-5
3-4
4-3,6
5-1
6-4

풀이) 1,N+1까지 탐색한다.
1번 노드를 시작 노드로 넣고 BFS 돌리면 visited로 2,5처리.
2, 5는 이미 방문으로 탐색 ㄴㄴ
그럼 3가서 4도 처리.
그럼 6가도 4는 이미 방문 안셈 (already visited)

from collections import deque
import sys
input = sys.stdin.readline

def bfs(i, graph, visited):
    q = deque()
    q.append(i)
    visited[i] = True
    while q:
        v = q.popleft()
        for node in graph[v]:
            # 검사조건 추가
            if not visited[node]:
                q.append(node)
                visited[node] = True

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

for i in range(1, N+1):
    if not visited[i]:
        bfs(i, graph, visited)
        count += 1
print(count)

bfs에 검사 조건을 어디 넣어줄 지 잘 생각해보자.
bfs로 날먹하지 말고 dfs도 연습 같이 해라.
그치만 재귀는 너무 싫은 걸.