본문으로 건너뛰기
김신건의 로그

Offline Incremental SCC, Parallel Binary Search

간선이 시간 순서로 추가되는 유향 그래프에서 두 정점이 같은 SCC 에 속한 최초 시각을 병렬 이분탐색으로 O((N+M) log T) 에 해결. 같은 mid 를 가진 쿼리들을 묶어 한 번의 SCC 판정으로 모두 처리.

메타데이터

ID offline-incremental-scc
카테고리 algorithm
버전 v4
길이 14.0s (14000ms)
구성 16 elements · 5 chapters · 5 effects
태그 #algorithm #graph #scc #parallel-binary-search

본문에 삽입

```anim:offline-incremental-scc
{}
```

이 애니메이션을 사용하는 글 (1)

사이트 검색 / 명령어

검색

스크롤 = 확대/축소 · 드래그 = 이동 · 0 = 원래 크기 · ESC = 닫기