Lv.3graphofflineunion-find
도로가 끊겨도 갈 수 있을까
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 마을과 양방향 도로 roads가 있습니다. roads[e] = [a, b]는 e번 도로가 a번과 b번 마을을 잇는다는 뜻입니다.
처음에는 모든 도로가 열려 있습니다.
폭설 때문에 도로가 하나씩 닫힙니다. 명령 배열 ops를 순서대로 처리하세요.
[1, e]:e번 도로가 닫힙니다. 닫힌 도로는 다시 열리지 않습니다.[2, a, b]: 지금 열려 있는 도로만 써서a번 마을에서b번 마을로 갈 수 있는지 확인합니다.
2번 명령의 결과(true/false)를 나온 순서대로 배열에 담아 반환하세요.
입출력 예
| n | roads | ops | result |
|---|---|---|---|
4 | [[0, 1], [1, 2], [2, 3], [0, 3]] | [[2, 0, 2], [1, 1], [2, 0, 2], [1, 3], [2, 0, 2], [2, 2, 3]] | [true, true, false, true] |
3 | [[0, 1]] | [[2, 1, 1], [2, 0, 2], [1, 0], [2, 0, 1]] | [true, false, false] |
입출력 예 설명
예 1 — 처음에는 원형으로 이어져 있습니다. 1번 도로(1–2)가 닫혀도 0 → 3 → 2로 갈 수 있습니다. 3번 도로(0–3)까지 닫히면 {0, 1}과 {2, 3}으로 나뉩니다.
예 2 — 같은 마을끼리는 항상 갈 수 있습니다. 2번 마을은 처음부터 고립되어 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, roads: int[][], ops: int[][]) → bool[]
제한 사항
-
n -
roads.length,a,b(같은 두 마을을 잇는 도로가 여러 개이거나a = b일 수 있습니다) -
ops.length [1, e]:e, 같은 도로가 두 번 닫히지는 않습니다.[2, a, b]:a,b.2번 명령은 적어도 하나 있습니다.
기대 복잡도
- 시간
- O((N + M + Q) α(N))
- 공간
- O(N + M + Q)
입출력 예
| n | roads | ops | 기대 출력 |
|---|---|---|---|
4 | [[0,1],[1,2],[2,3],[0,3]] | [[2,0,2],[1,1],[2,0,2],[1,3],[2,0,2],[2,2,3]] | [true,true,false,true] |
3 | [[0,1]] | [[2,1,1],[2,0,2],[1,0],[2,0,1]] | [true,false,false] |
힌트
힌트
유니온 파인드는 두 무리를 합치기는 잘하지만 끊기는 못 합니다. 그렇다면 시간을 거꾸로 돌려 보세요.
마지막 명령까지 처리한 뒤의 상태, 즉 한 번도 닫히지 않은 도로만 열린 상태에서 시작해 명령을 뒤에서부터 봅니다.
- 거꾸로 보면
[1, e]는 도로가 다시 열리는 사건이므로union(a, b)를 합니다. [2, a, b]는 그 시점의 상태 그대로find(a) == find(b)로 답하고 기록합니다.
모든 명령을 미리 알고 있으므로(오프라인) 가능한 방법입니다. 기록한 답은 마지막에 원래 순서로 뒤집어 반환하세요.
복잡도 목표
질문마다 BFS/DFS로 길을 찾으면 이 되어 효율성 테스트에서 시간 초과가 납니다. 거꾸로 처리하면 거의 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 360 ms | 추정 |
| C++ (GCC, gnu++23) | 360 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1928 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1720 ms | 추정 |
| C# 14 (.NET 10) | 1720 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |