Lv.4dfsgraphscc
서로 오갈 수 있는 무리
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 지점과 일방통행 길 edges가 있습니다. edges[i] = [a, b]는 a에서 b로만 갈 수 있는 길입니다.
두 지점 u, v가 u → v로도, v → u로도 (다른 지점을 거쳐서라도) 갈 수 있으면 같은 무리로 봅니다. 모든 지점은 자기 자신과 같은 무리입니다.
[무리의 개수, 가장 큰 무리의 지점 수]를 반환하세요.
입출력 예
| n | edges | result |
|---|---|---|
5 | [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]] | [3, 3] |
4 | [[0, 1], [1, 0], [2, 3], [3, 2], [1, 2]] | [2, 2] |
3 | [] | [3, 1] |
입출력 예 설명
예 1 — {0, 1, 2}는 순환이라 서로 오갈 수 있습니다. 3과 4는 되돌아올 길이 없어 각자 무리입니다.
예 2 — {0, 1}과 {2, 3} 두 무리입니다. 1 → 2는 한쪽으로만 가므로 합쳐지지 않습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, edges: int[][]) → int[]
제한 사항
-
n -
edges.length edges[i] = [a, b], . 같은 길이 여러 번 나오거나a == b일 수 있습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| n | edges | 기대 출력 |
|---|---|---|
5 | [[0,1],[1,2],[2,0],[2,3],[3,4]] | [3,3] |
4 | [[0,1],[1,0],[2,3],[3,2],[1,2]] | [2,2] |
3 | [] | [3,1] |
힌트
힌트
강한 연결 요소(SCC) 문제입니다. 코사라주 알고리즘이 이해하기 쉽습니다.
- 원래 그래프에서 DFS를 돌며 끝난 순서(후위 순서)대로 지점을 기록합니다.
- 모든 길을 뒤집은 그래프에서, 1단계 기록의 역순으로 아직 무리가 없는 지점을 골라 DFS합니다. 한 번의 DFS가 닿는 지점들이 정확히 한 무리입니다.
타잔 알고리즘(low-link)으로 한 번의 DFS에 끝낼 수도 있습니다.
지점이 10만 개라 길이 한 줄로 이어지면 재귀 깊이가 10만이 됩니다. 명시적 스택으로 반복문 DFS를 쓰세요.
복잡도 목표
지점마다 앞뒤로 탐색해 무리를 하나씩 찾는 방식은 무리가 많을 때 이라 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 222 ms | 추정 |
| C++ (GCC, gnu++23) | 222 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1414 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1444 ms | 추정 |
| C# 14 (.NET 10) | 1444 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 8 | 판정만 |
| performance | 60 | 4 | 판정만 |