끊기면 안 되는 도로
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 도시와 양방향 도로 roads가 있습니다. roads[i] = [a, b]는 i번 도로입니다.
어떤 도로 하나가 끊겼을 때, 원래는 오갈 수 있던 두 도시가 더 이상 오갈 수 없게 된다면 그 도로를 끊기면 안 되는 도로라고 합니다.
끊기면 안 되는 도로의 번호를 오름차순으로 정렬해 반환하세요. 없으면 빈 배열입니다. 같은 두 도시를 잇는 도로가 여러 개면, 그중 하나가 끊겨도 다른 도로로 갈 수 있습니다.
입출력 예
| n | roads | result |
|---|---|---|
5 | [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]] | [3, 4] |
2 | [[0, 1], [1, 0]] | [] |
4 | [[0, 1], [2, 3]] | [0, 1] |
입출력 예 설명
예 1 — 0-1-2는 삼각형이라 한 변이 끊겨도 돌아갈 수 있습니다. 1-3(3번), 3-4(4번)는 끊기면 3, 4번 도시가 떨어져 나갑니다.
예 2 — 같은 두 도시를 잇는 도로가 두 개입니다.
예 3 — 그래프가 두 덩어리로 나뉘어 있어도 각 도로는 끊기면 안 되는 도로입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, roads: int[][]) → int[]
제한 사항
-
n -
roads.length roads[i] = [a, b], , . 같은 두 도시를 잇는 도로가 여러 개 있을 수 있습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| n | roads | 기대 출력 |
|---|---|---|
5 | [[0,1],[1,2],[2,0],[1,3],[3,4]] | [3,4] |
2 | [[0,1],[1,0]] | [] |
4 | [[0,1],[2,3]] | [0,1] |
힌트
힌트
단절선(브리지) 찾기, 타잔(Tarjan)의 low-link 알고리즘입니다.
DFS를 하면서 각 도시에 방문 순서 tin[v]를 매기고,
low[v] = "v의 DFS 서브트리에서 트리 간선이 아닌 간선 하나를 써서 닿을 수 있는 가장 이른 방문 순서"를 계산합니다.
트리 간선 u → v에 대해 low[v] > tin[u]이면, v 쪽 서브트리는 그 간선 말고는 위로 올라갈 길이 없으므로 단절선입니다.
주의할 점 두 가지.
- 같은 도시 쌍을 잇는 도로가 여러 개일 수 있으니, "부모로 돌아가는 간선"은 부모 도시가 아니라 들어온 도로 번호로 건너뛰세요.
- 도시가 10만 개라 한 줄로 이어진 그래프에서는 재귀 깊이가 10만이 됩니다. 반복문(명시적 스택)으로 DFS를 구현하는 편이 안전합니다.
복잡도 목표
도로를 하나씩 지워 보며 연결 여부를 다시 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1738 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 8 | 판정만 |
| performance | 60 | 4 | 판정만 |