DHistory
[Baekjoon] DFS/BFS - 11724 연결 요소의 개수 본문
문제
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어
www.acmicpc.net
풀이
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().rstrip().split())
visited = [False] * (n + 1)
graphs = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().rstrip().split())
graphs[a].append(b)
graphs[b].append(a)
def solution(graphs, start, visited):
if visited[start]:
return False
queue = deque([start])
visited[start] = True
while queue:
now = queue.popleft()
for v in graphs[now]:
if not visited[v]:
queue.append(v)
visited[v] = True
return True
answer = 0
for i in range(1, n + 1):
if solution(graphs, i, visited):
answer += 1
print(answer)
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DFS/BFS - 11725 트리의 부모 찾기 (0) | 2023.09.06 |
|---|---|
| [Baekjoon] DFS/BFS - 4963 섬의 개수 (0) | 2023.09.04 |
| [Baekjoon] DFS/BFS - 1012 유기농 배추 (0) | 2023.09.04 |
| [Baekjoon] DFS/BFS - 1260 DFS와 BFS (0) | 2023.09.04 |
| [Baekjoon] DFS/BFS - 2606 바이러스 (0) | 2023.09.04 |