1. Cut Vertex Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 O(n (m+n))의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 O(m+n)만에 절단점을 찾을 수 있다. 1.2. root Cut Vertex root 노드는 child가 2개 이상이라면 무조건 cut vertex이다. 증명해보자! 1) child가 0개인 경우 루트 노드밖에 없으므로 성립 2) child가 1개인 경우 사진과 같이 root노드가 없어도 자식노드들 끼리 다 연결되어있다. 3) child가 2개 이상일 경우 루트노드에 1번 서브트리와 2번 서브트리가 있다고 가정해보자. 1번 서브트리에는 어딘가에 ..
