알고리즘21

자신의 pre번호, 자신이 올라갈 수 있는 pre번호, 자신의 subtree에서 올라갈 수 있는 pre번호 중 가장 작은 것

 

셋 중 하나라도 못올라가는 게 있으면 t는 cut vertex

 

 

 

---

Cut Edge

: 이 엣지가 사라지면 그래프가 끊어진다.

 

 

 

모든 엣지마다 빨간 노드를 넣는다.

(엣지 하나를 끊고 2개로 나눈다.)

엣지마다 노드가 추가되었으므로

노드 = m개

엣지 = 2m개

 

nxm -> mxm

 

dfs돌려서 Cut Vertex를 찾는다.

빨간 노드 중에 Cut Vertex가 있는지 찾는다.

 

---

BCC (Biconnected Component)

Cut Vertex의 의미가 더 크다(?)

 

cut edge와 cut vertex를 생각해보자.

cut edge는 없다.

cut vertex는 있다. 이 그래프는 사실 BCC에 의해 두 덩어리라고 얘기할 수 있다.

 

Biconnected Component: 한 노드에서 다른 노드를 연결하는 path가 완전히 독립적인 path가 2개 이상 있을 때

 

Cut Vertex가 사라지면 Biconnected 상태가 아님 (밀접한 관계)

Cut Vertex가 있으면 그래프 전체가 Biconnected인 것이 아니다.

 

cut vertex를 나누어 생각하면,

왼쪽 4개, 오른쪽 4개만 보면 각각 Biconnected이다.

 

 

cut edge와 cut vertex가 둘 다 있는 예시

 

---

 

DFS를 하다가 cut vertex에서 멈추자.

한번에 도는 곳이 BCC이다. => 안됨!

 

<안되는 예시>

BCC가 5개임. (cut vertex가 색칠된 노드)

cut vertex에서 멈추면 다음으로 못넘어간다.

 

(3개와 공유할 수도 있음)

cut vertex를 root로두고 DFS로 돌리면 이렇게 나옴

Child 2개

 

즉 트리의 child가 3개면 덩어리가 3개로 나누어졌다는 뜻

 

각 BCC에 들어갈 그룹을 나누는법

1. 서브에서 백엣지로 루트까지 올라가면 루트는 BCC에 포함

2. 서브에서 백엣지로 루트까지 올라가지 않는다면 루트는 BCC에 포함되지않음

 

3. 루트 위로 백엣지가 올라가면 루트와 서브가 같은 덩어리에 포함된다는 뜻. 루트와 크게 상관없는 BCC

 

---

Topological Sort 

: 모든 링크가 왼쪽에서 오른쪽으로 가도록 한 줄로 sorting하기

 

 

DAG: 방향성이 있고 사이클이 없는 그래프 

그래프 전체에 방향성을 부여할 수 있다.

의존도에 사용(ex - 옷을 입을 때 무엇을 먼저입어야 한다.)

속옷을 입고 옷을 입어야 하지만, 양말과 모자는 상관없다

동시에 먼저할 수 없으므로 사이클x

 

 

 

- 사이클이 있으면 불가능

사이클이 있는 노드를 한줄로 세웠다면 어떻게 세웠든 제자리로 돌아온다.

 

 

- 사이클이 없으면 항상 가능한가?

=> 가능하다 (알고리즘으로 증명가능)

 

 

---

한 가지 관찰로부터 시작한다.

한 가지 관찰로부터 시작한다.

 

indegree가 0인 노드가 최소 하나 있어야 한다.

 

 

 

 

indegree가 0인 노드가 없다면,

노드를 따라 들어가는 과정이 멈출 수 없다.

-> 같은 노드를 2번가는 경우가 생긴다. (사이클)

 

=> 사이클이 없다면 indegree가 0인 노드가 있다

 

 

indegree가 0 인 노드를 삭제하고 남은 것도 DAG(방향성 비순환 그래프)

원래 사이클이 없던 그래프니까 제거해도 사이클이 없다. (당연)

 

 

 

G'을 topological sort 할 수있으면 G를 topological sort 할 수있다 (재귀의 step부분)

 topological sort = 위상정렬(모든 엣지가 한방향으로 간다) (사이클이 없다면 항상 가능)

 

이것은 느린 알고리즘 O(NM)

 

indegree 계산 = O(n+m)

이걸로 노드하나 제거

G' 도 O(n+m) 와 비슷한 시간

 

문제는 하나를 제거하기 위해서 degree count를 했는데

계산하는 것을 줄여버리면 시간을 많이 줄일 수 있다.

 

 

 

indegree=0인 노드를 전부 큐에 넣는다.

원래 indegree가 0 인 애들은 큐에 들어가 있음

새로 indegree가 0이 된 노드가 있느냐? ㅇㅇ

 

출력이 V라면 V와 연결된 노드의 indegree를 업데이트해주면 여기서 0이 나올 수 있다.

오른쪽에서 왼쪽으로 가는 엣지는 없다.

이미 출력된 노드로 가는 링크는 없다.

indegree가 0인 상태에서 출력되었으므로