https://www.acmicpc.net/problem/9372
비행기의 종류가 최소가 되어야 한다고 해서 순간 헷갈렸는데, 그냥 dfs로 그래프를 탐색하면서 모든 나라를 방문할때까지 이동하는 횟수를 카운트하면 되는 간단한 문제였다.
import sys
input = sys.stdin.readline
T = int(input())
def dfs(v):
global cnt, ans
visit[v] = True
cnt += 1
if (cnt==N):
return
for i in plane[v]:
if (visit[i]==False):
ans += 1
dfs(i)
for _ in range(T):
N, M = map(int, input().split())
plane = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
plane[a].append(b)
plane[b].append(a)
visit = [False]*(N+1)
cnt = 0
ans = 0
dfs(1)
print(ans)
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 14940번: 쉬운 최단거리 (0) | 2021.08.14 |
---|---|
BOJ 2210번: 숫자판 점프 (0) | 2021.08.12 |
21316번: 스피카 (0) | 2021.08.08 |
BOJ 14496번: 그대, 그머가 되어 (0) | 2021.05.25 |
BOJ 18352번: 특정 거리의 도시 찾기 (0) | 2021.05.25 |