Funcia
Lv.4dfsgraphscc

서로 오갈 수 있는 무리

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

0번부터 n - 1번까지 n개의 지점과 일방통행 길 edges가 있습니다. edges[i] = [a, b]는 a에서 b로만 갈 수 있는 길입니다.

두 지점 u, v가 u → v로도, v → u로도 (다른 지점을 거쳐서라도) 갈 수 있으면 같은 무리로 봅니다. 모든 지점은 자기 자신과 같은 무리입니다.

[무리의 개수, 가장 큰 무리의 지점 수]를 반환하세요.

입출력 예

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

제한 사항

  • 1≤1 \le n ≤100,000\le 100{,}000
  • 0≤0 \le edges.length ≤200,000\le 200{,}000
  • edges[i] = [a, b], 0≤a,b<n0 \le a, b < n. 같은 길이 여러 번 나오거나 a == b일 수 있습니다.

기대 복잡도

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

입출력 예

nedges기대 출력
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) 문제입니다. 코사라주 알고리즘이 이해하기 쉽습니다.

  1. 원래 그래프에서 DFS를 돌며 끝난 순서(후위 순서)대로 지점을 기록합니다.
  2. 모든 길을 뒤집은 그래프에서, 1단계 기록의 역순으로 아직 무리가 없는 지점을 골라 DFS합니다. 한 번의 DFS가 닿는 지점들이 정확히 한 무리입니다.

타잔 알고리즘(low-link)으로 한 번의 DFS에 끝낼 수도 있습니다.

지점이 10만 개라 길이 한 줄로 이어지면 재귀 깊이가 10만이 됩니다. 명시적 스택으로 반복문 DFS를 쓰세요.

복잡도 목표

지점마다 앞뒤로 탐색해 무리를 하나씩 찾는 방식은 무리가 많을 때 O(N(N+M))O(N(N + M))이라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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