SCC & BCC
SCC 설명 SCC 개념 및 특징 Strongly Connected Components / 강한 연결 요소 단방향 그래프의 같은 SCC에 속한 임의의 두 정점 (u, v) 쌍에 대해서 u에서 v, v에서 u로 향하는 경로가 존재합니다. maximal한 성질을 갖고 있어서, SCC가 가능한 커야 합니다. 예를 들어서 아래 그림에서 정점 a와 b끼리 서로를 향한 경로가 존재하지만, maximal한 성질이 있으므로 a, b, e가 SCC가 됩니다. SCC끼리 새로운 그래프로 구축하면 DAG가 되며, 이를 통해 위상 정렬할 수 있습니다. SCC 구현 방법 대표적으로 코사라주 알고리즘과 타잔 알고리즘이 있습니다. Kosaraju Algorithm (코사라주 알고리즘) DFS 두 번으로 구할 수 있으며, 역방향 그..
알고리즘
2021. 11. 6. 14:11