여기서 Cut Vertex찾는거
Cut Vertex
원래 입력 : 연결된 그래프가 주어짐
연결된 그래프 중 제거했을 때 그래프가 끊어지는게 되는 거를 찾을 거임
어떤 시간에? O(n+m)시간에 찾을거임
이것보다 느리게는 쉬움
이미 알고 있는 방법
어느 한 군데에서 reachability를 해서 전체로 가는지, 중간에 끊어졌는지 확인
1번 노드 빼고 reachability, 2번 노드 빼고 reachability .... n번 노드 빼고 reachability
시간은? reachability한번 할 때 마다 n+m
이걸 n번 하니깐
총 시간 O(n(n+m))
알고리즘 하나하나는 local한 정보 밖에 못 봄
노드가 다른 노드한테 자기가 없으면 다른 길이 있냐고 물어봄
근데 이 상태로는 답하기 힘듬
그래서 DFS로 답할 수 있는 global한 정보 만듬
문제를 이렇게 바꿀 수 있음
노드 V가 cutvertex -> 어떤 노드 x,y가 있어서 모든 (x->y)path가 v를 지나감
방법
DFS돌림 그러면 Tree가 만들어짐
이 트리에서 root노드는 cut-vertex인지 아닌지 쉽게 알 수 있음
why? cross edge가 존재하지 않기 때문
root의 child가 하나밖에 없는 경우와 두 개 이상인 경우 생각
하나인 경우
두 개 이상인 경우
root는 반드시 cut-vertex
좋은 방법 root를 바꿔가며 dfs를 해보는 것
그럼 시간이?
DFS n번 돌림
-> O(n^2)
DFS한번 돌리고 루트가 아닌 노드들에 대해서 풀어줘야함
만약 V와 나머지 노드를 거치지 말라고 하면 못가는 건 맞음
그렇다고 해서 V가 cut-vertex가 되는건 아님
실제로 V를 안거치고 다른데로 돌아서 갈 수 있음
모든 노드V에 대해서 l(v)라는 값을 계산할 거임
l(v)는 dynamic programming으로 계산
(트리 아래쪽부터 dynamic programming돌려서 올라옴)
*여기서 pre(v)를 구하는 것은 쓸모없어 보일 수 있지만 v가 만약 back edge가 없는 리프노드라면 l(v)가 정의가 안되기 때문에 필요하다.
l(u)가 pre(v)보다 값이 크면
y는 back-edge, tree-edge를 아무리 타고 돌아다녀도 u에서 v로 올라오지 않는 한 자기 sub-tree에 갇힌 상태가 됨
l(u)가 pre(v)하고 같으면
back-edge타고 v까지는 올 수 있지만 그 위로는 못감 -> 여전히 갇힘
l(u)가 pre(v)보다 작으면
밖으로 나올 수 있다(sub-tree밖으로 나올 수 있다).
드디어 v가 cut-vertex인지 판단할 수 있는 방법 나옴
child한테 물어봄
너 나 안거치고 다른 데 갈 수 있어? -> l(u)가 pre(v)보다 크거나 같으면 못가는 거고, 작으면 갈 수 있다.
못간다고 하는 child가 하나라도 있으면 v는 cut-vertex가 됨
모든 노드에 대해서 l값을 구한다음에 노드 v를 보고 노드v의 child들의 l값 물어봄 l값이 v보다 크거나 같은게 하나라도 있으면 v가 cut-vertex
그럼 그림에서 v가 cut-vertex면 u도 cut-vertex가 되는가?
-> 그건 아님
l(v)계산하는 방법
자기 child들의 l값 정해져 있으면 계산할 수 있다.
DFS tree만들고 그걸 traversal하면 서 계산할 수도 있고,
DFS tree를 만들면서도 할 수 있음(계산하고 떠나는 방식)
DFS traversal하면서 child를 다 부르고 나면 child값 계산
그걸 받아서 내가 계산하고 그 값을 parent에 줄 수 있다.
(아래에서 위로 올라오는 dp)
시간
l값 계산 : DFS하면서 다 계산할 수 있음(2번해도 되고) : n+m
각각이 cut-vertex인지 판단 : 그냥 child들만 보고 비교 -> 노드마다 상수 시간(child개수 만큼 걸림 -> 전체를 보면 엣지 개수(m)만큼 시간을 씀)
-> O(n+m)
Cut Edge
Edge가 cut-Edge인지 판단은 어떻게?
