๋ฌธ์
https://www.acmicpc.net/problem/2606
๋ฐฑ์ค ๋จ๊ณ๋ณ๋ก ํ์ด๋ณด๊ธฐ - ๊ทธ๋ํ์ ์ํ
ํ์ด
์ด๋ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค. ์ปดํจํฐ์ ์์ ๋คํธ์ํฌ ์์์ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ปดํจํฐ == ๋
ธ๋๋ก ์๊ฐํ๊ณ , 1๋ฒ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๊ฐฏ์๋ฅผ ๊ตฌํ๋ค.
DFS, BFS ๋ชจ๋ ์ ํ ๊ฐ๋ฅํ ๋ฌธ์ ๋ค.
๋จผ์ ๋น ๋ฆฌ์คํธ๊ฐ ํฌํจ๋ 2์ฐจ์ ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ค์, ์ฃผ์ด์ง ๋
ธ๋๋ค์ ์๋ฐฉํฅ์ผ๋ก ์ ์ฅํ๋ค.
์ง์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ผ๋ฆฌ๋ง ์ํฅ์ ์ฃผ๋๊ฒ ์๋๊ณ , 1๋ฒ ์ปดํจํฐ๋ก๋ถํฐ ํ์๋ ๋ชจ๋ ์ปดํจํฐ๋ค์ ๋ชจ๋ ๊ฐ์ผ๋๋๊ฒ์ด๊ธฐ ๋๋ฌธ์ด๋ค.
network = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().split())
network[u].append(v)
network[v].append(u)
ex) ๋จ๋ฐฉํฅ์ผ๊ฒฝ์ฐ, ๋ง์ฝ ์์ 1์์ 2 3์ด 3 2๋ก ๋ณ๊ฒฝ๋๋ค๋ฉด?
https://www.acmicpc.net/board/view/9978
7
6
1 2
3 2
1 5
5 2
5 6
4 7
๋จ๋ฐฉํฅ์ผ๋ก ์ ์ฅ ์ 2๋ฒ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ ธ๋๊ฐ ์๋ค๊ณ ํ๋จ๋๋ฏ๋ก 3๋ฒ ์ปดํจํฐ๊ฐ ๋ฐฐ์ ๋๋ค.
๊ทธ๋ฆฌ๊ณ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ค์ ์ฒดํฌํด์ผํ๋ฏ๋ก N+1๋งํผ์ ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ค.
visited = [False] * (N+1)
๋๋ถ๋ถ์ ๋ฌธ์ ์์ ๋
ธ๋๋ฒํธ๋ 1๋ถํฐ ๋ถ์ฌ๋๋ฏ๋ก N+1๋ก ๋ง์ถฐ์ฃผ๋๊ฒ ํธํ๋ค. (์ด ๋ฌธ์ ์ญ์ ๊ทธ๋ฌํ๋ค.)
๋ง์ง๋ง์ผ๋ก DFS๋ฅผ ํตํด ๋
ธ๋๋ค์ ๊ฐฏ์๋ฅผ ๊ตฌํ ๋ค, -1ํ ๊ฐ์ ์ถ๋ ฅํ๋ค.
1๋ฒ ์ปดํจํฐ๋ ์์ฃผ์ด๋ฏ๋ก ๊ฐ์ผ ๋์์์ ์ ์ธ๋๋ค.
์ ์ฒด ์ฝ๋
# ๊ทธ๋ํ์ ์ํ
# 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ๊ฐ์ผ๋ ์ปดํจํฐ์ ๊ฐฏ์๋ฅผ ์ถ๋ ฅ.
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 32ms
from sys import stdin
input = stdin.readline
N, M = int(input()), int(input())
network = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().split())
network[u].append(v)
network[v].append(u)
visited = [False] * (N+1)
def checking():
stack = [1]
while stack:
c = stack.pop()
if not visited[c]:
visited[c] = True
for v in network[c]:
if not visited[v]:
stack.append(v)
return sum(visited) - 1 # 1๋ฒ ์ปดํจํฐ๋ ๊ฒฐ๊ณผ์์ ์ ์ธํด์ผํจ.
print(checking())
DFS, BFS ์ฐ์ต๋ฌธ์ ๋ค. ์๊ณ ๋ฆฌ์ฆ ์์ 24479~ ๋ค์์ ๋ฐ๋ก ์์นํ ๋ฌธ์ ์ธ๋ฐ, ์ด๋๋ง ํด๋ 'DFS, BFS๊ฐ ์ ํํ ๋ญ์ง + ์ด๋ป๊ฒ ๊ตฌํํ๋๊ฑฐ์ง? + ์ ์ด๋ ๊ฒ ๊ตฌํํ๋๊ฑฐ์ง??' ์ฝค๋ณด๋ก ํค๋กฑํค๋กฑํ๋ ๊ธฐ์ต์ด ๋๋ค.
๊ฒฐ๋ก ์ ๋ ธ๋ ์ ์ฅ ์ ์๋ฐฉํฅ/๋จ๋ฐฉํฅ ํ๋จ์ ์ฃผ์ํ์.