Funcia
Lv.3graphofflineunion-find

도로가 끊겨도 갈 수 있을까

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
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)를 나온 순서대로 배열에 담아 반환하세요.

입출력 예

nroadsopsresult
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[]

제한 사항

  • 1≤1 \le n ≤200,000\le 200{,}000
  • 0≤M=0 \le M = roads.length ≤200,000\le 200{,}000, 0≤0 \le a, b <n< n (같은 두 마을을 잇는 도로가 여러 개이거나 a = b일 수 있습니다)
  • 1≤Q=1 \le Q = ops.length ≤200,000\le 200{,}000
  • [1, e]: 0≤0 \le e <M< M, 같은 도로가 두 번 닫히지는 않습니다.
  • [2, a, b]: 0≤0 \le a, b <n< n. 2번 명령은 적어도 하나 있습니다.

기대 복잡도

시간
O((N + M + Q) α(N))
공간
O(N + M + Q)

입출력 예

nroadsops기대 출력
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로 길을 찾으면 O(Q⋅(N+M))O(Q \cdot (N + M))이 되어 효율성 테스트에서 시간 초과가 납니다. 거꾸로 처리하면 거의 O(N+M+Q)O(N + M + Q)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)360 ms추정
C++ (GCC, gnu++23)360 ms도출됨
Python 3.131000 ms도출됨
Java 251928 ms도출됨
Kotlin 2.4 (JVM)1720 ms추정
C# 14 (.NET 10)1720 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.