알고리즘
알고리즘21-2
yerintil
2020. 11. 20. 14:58
728x90
2배 가까이 빠르다.
기존 방법은 DFS를 통해indegree를 알아냈다.
이 방법은 directed 그래프에서 DFS하는 방법. 엣지 방향을 맞춰서 전진해야 한다. (post order로 번호)
post번호가 줄어드는 순서대로 출력한다.
or
post번호를 계산하는 순간 노드를 출력할 수 있다. (모든 엣지가 오른쪽->왼쪽이 된다.)
사이클이 있을 수있으므로 back edge, forward edge가능
cross edge는 무조건 오른쪽에서 왼쪽으로.
왼쪽에서 오른쪽으로는 갈 수가 없다. 왼쪽부터 도는건데 밑에 노드로 있었겠지
DAG는 백엣지가 없다.
이 상태에서 알고리즘 정당화하겠다.
먼저간걸 왼쪽에 그리고 트리 order대로 그리면 무조건 이순서
(왼쪽이 번호가 작고 위로갈수록 크다)
큰번호->작은번호
백엣지는 작은번호 -> 큰번호인데 없음
크로스엣지는 큰번호 -> 작은번호
=> post로 번호를 붙이면 모든 엣지가 큰번호에서 작은번호로 간다.
DFS를 어디서 시작 하느냐에 따라 트리 갯수자체가 달라진다.
트리 갯수는 알 수 없지만 성질은 항상 성립한다.
관련문제
모든 노드가 양쪽으로 reachable해야 한다.
전체를 scc라고 한다. (maximal)
정의 : 그래프가 주어졌을 때 SCC를 찾는 문제!
DFS를 했더니, 한 SCC는 한 Tree 안에 있다.
한 SCC가 두 트리에 나눠져있을 수 없다.