어디서든 오갈 수 있게 길 더하기

레벨 E2 · 코딩 · JavaScript · 목표 시간 33분 · 게시일 2026-11-01

0번부터 n-1번까지의 도시와 일방통행 도로 roads([a, b]는 a에서 b로 가는 도로)가 주어진다. 새 일방통행 도로를 몇 개 더 지어 어느 도시에서든 다른 모든 도시로 갈 수 있게 만들려고 한다. 더 지어야 하는 도로 수의 최솟값을 구하시오. 이미 그렇다면 0이다.

n은 최대 50,000, 도로는 최대 100,000개이다. 같은 도로가 여러 번 나오거나 a = b인 도로가 있을 수도 있다. 도시마다 탐색을 새로 하는 방법으로는 시간 안에 끝나지 않으며, 깊은 재귀도 피하시오.

예제

solve(4, [[0,1],[1,2],[2,0],[2,3]])
solve(3, [[0,1],[1,2],[2,0]])
solve(3, [])

E2 레벨의 다른 문제 · 코딩 문제 목록