Bridge( 절선 ), Articualtion point( 절점 ) 찾기

임의의 한 지점에서 다른 모든 지점으로 갈수 있는 경로가 있는 양방향 그래프  G가 있다고 하자.
G에서 어떤 간선 하나가 삭제 되었을 때 G가 2개이상의 그래프로 분리된다면 이 간선을 절선(Bridge) 이라고 한다.

G에서 어떤 정점 v가 삭제 되었을 때(v에 연결된 모든 간선도 같이 삭제) G가 2개 이상의 그래프로 분리 된다면 이 정점을 절점(Articualtion point) 이라고 한다.

절점과 절선을 구하기 위해 그래프를 트리에 backedge 가 달려 있는 상태로 만들어보자.

----- 그림 추가 예정 ---
즉 무방향 그래프를 방향 그래프로 만들어 준다.


dfn[v] : DFS로 방문된 순서
back[v] :  v에서 시작하여 트리 에지와 하나의 백 에지를 통해 도달 가능한 루트에 가장 가까운 정점의 dfn

process :
1. 처음으로 정점 v를 방문하는 경우:
 back[v] = dfn[v]로 초기화

2. 백 에지(v,w) 를 만나는 경우 :
back[v] = min( back[v], dfn[w] )

3. 트리 에지 (v,w)를 만나는 경우 :
back[v] = min( back[v], back[w] )

정점 v가 절점이기 위한 필요 충분 조건
1. 자식을 2개 이상 갖는 루트
2. dfn[v] <= back[w] 인 자식 노드 w가 있는 경우

간선 (v-w)가 절선이기 위한 필요 충분 조건
1. v가 부모 노드이고 w가 자식 노드 일 때 dfn[v] < back [w]

절점 이용 문제 : 병원균퇴치 : http://koistudy.net/?mid=prob_page&NO=1044&SEARCH=0
절선 이용 문제 :  공중도시(KOI 2015 지역본선 고등) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2127%20&sca=50