BOJ 11724 연결 요소의 개수
6274 단어 2021.01.162021.01.16
https://www.acmicpc.net/problem/11724
시간 3초, 메모리 215MB
input :
- N M (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
- u v(1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만
output :
- 연결 요소의 개수를 출력한다.
무방향 그래프? 양방향 그래프와 동일한 것 같다.
visit 리스트에 False가 남아 있냐로 구분하면 된다.
그리고 graph를 저장 할 때도 0을 빼고 시작 했기 때문에 for문으로 BFS를 돌릴 때 (1, n + 1)번 만큼 돌려 주어야 한다.
import sys
from _collections import deque
n, m= map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
def BFS(start):
q = deque([start])
visit[start] = True
while q:
now = q.popleft()
for i in graph[now]:
if not visit[i]:
q.append(i)
visit[i] = True
return cnt
visit = [False] * (n + 1)
visit[0] = True
cnt = 0
for i in range(1, n + 1):
if not visit[i]:
BFS(i)
cnt += 1
print(cnt)
Author And Source
이 문제에 관하여(BOJ 11724 연결 요소의 개수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-11724-연결-요소의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)