cksdnwh   2년 전

SCC알고리즘을 공부하고 주어진 그래프를 SCC로 나누는 데까지는 했습니다.

위의 SCC를 어떤식으로 써먹어야할지 감이  안 와서 고수님들께 물어보고싶습니다.

아시는 분들 말씀 좀 해주세요 ㅠㅠ

Green55   2년 전

SCC를 써도 결국 묶을 수 없는 그래프(즉, DAG)가 주어질 수 있기 때문에 이 문제에서는 SCC를 쓴다고 결국엔 시간복잡도를 바꿀 수 없습니다.

이 문제는 단순히 N번 [O(N)], DFS 또는 BFS [O(N+M)]를 돌려 O(N^2+NM)으로도 충분히 통과 가능합니다.

cksdnwh   2년 전

생각해보니 그렇군요 감사합니다!

kipa00   2년 전

DAG의 경우 cycle이 없다는 특성상 시간 복잡도를 (SCC 후) O(N^2 + M)으로 줄일 수 있습니다. cycle이 없기 때문에, memoization을 통해 각 group에 대해 어떤 group에 도달할 수 있는지 여부를 빠르게 구할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.