알고리즘21-2

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가 두 트리에 나눠져있을 수 없다.