2JINISHAPPY 2JINISHAPPY

DAG는 Topological Sort, Strongly Connected Component 등을 정의할 때 자주 사용되는 자료구조로 사이클이 존재하지 않는 방향 그래프 를 의미한다 DAG를 이해하기 위해 Directed graph G가 cycle이 있다 ↔ G의 DFS Tree가 back edge를 가지고 있다 이러한 성질들은 서로 필요충분조건을 만족한다는 사실을 알 필요가 있다 1️⃣ ⬅ (G의 DFS Tree가 back edge를 가지고 있다면 G에는 cycle이 존재한다) : 그래프 G에서 임의의 정점 u와 v에 대해 back edge(v,u)가 존재한다고 가정한다(위의 그림). 그러면 u ➡ ... ➡ v ➡ u로의 cycle이 존재한다 2️⃣ ➡ (Directed Graph G가 cycle이 ..