====== Split the SSHS 2 ======

===== 풀이 =====
  * [[ps:problems:boj:17098]]과 매우 비슷한 문제이다. 사실 [[ps:problems:boj:17098]] 보다 이 문제가 더 어려워보이는데, 난이도는 더 쉽게 매겨져있다..
  * 정점 세 개를 골라 그 정점들을 연결하는 엣지들을 지우는 것이므로, 엣지는 최소 0개에서 최대 3개까지 지워질수 있다. 정점 세개 간에 엣지가 하나도 없다면 지워봤자 바뀌는 것이 없으므로 신경쓰지 않아도 된다. 그러므로 지워야 하는 엣지들을 두 정점 사이의 엣지 1개와, 두 정점들과 세번째 정점 사이의 엣지들 0~2개라고 생각해도 된다.
  * 두 정점 사이의 엣지가 단절선이라면, 세번째 정점에 관계 없이 그래프가 분리된다. [[ps:problems:boj:17098]]과 똑같다. 단절선 하나를 잡으면, 세번째 점은 N-2 개중에서 아무거나 고르면 되니까, 이러한 형태의 개수는 {단절선의 개수} * (N-2) 가 된다. 여기에서 중복 카운팅을 제거해야 하는데, (u,v,w)에 대해서 u-v가 단절선이고, v-w가 단절선인 경우의 개수를 세어주면 된다. u-v,v-w,w-u 가 모두 단절선이 되는 경우는 존재하지 않으므로 생각하지 않아도 된다. 
  * 이제, u,v,w 사이의 엣지들 중에서 단절선이 없는 경우를 세어주면 된다. 이것도 [[ps:problems:boj:17098]]과 마찬가지이다. u,v,w가 같은 BCC안에 있고, u-v-w 형태로 엣지가 있고, 그 BCC 안에서 v와 연결된 다른 노드가 없으면, u,v,w 이 답이 된다. BCC 마다 그 BCC안에 해당되는 노드와 엣지들만으로 그래프를 그려서 각 노드들의 차수를 구한다음에, 차수가 2인 노드 (v의 역할)을 찾아주면 된다. [[ps:problems:boj:17098]]과 다른 점은 여기에서도 중복 카운팅이 생길수 있다는 점이다. (u,v,w)을 골랐을때, v뿐 아니라, u나 w도 조건을 만족할수 있다. 이를테면 u도 BCC 안에서 연결된 노드들이 v와 w밖에 없는 경우가 있을 수 있다. 이 경우를 좀더 생각해보자. u와 v가 둘다 그러한 조건을 만족한다면 w 역시 같은 조건을 만족한다는 것을 알수 있다. w가 u,v 외에 다른 노드 x와 연결되어있다면 w를 제거하면 x와 u,v 가 분리되므로, w가 단절점이 되고 x와 u는 같은 BCC에 있다는 전제에 모순이 된다. 결국, 중복 카운팅이 생기는 경우는 u,v,w 가 모두 서로에게만 엣지가 있는 경우이고, 이때는 (u,v,w)만으로 BCC를 이루게 된다. 그러므로, BCC중에서 크기가 3인 경우만 따로 세어주면 쉽게 처리된다.
  * 그래프를 BCC로 분리한 뒤, BCC들에 대해서 수행하는 여러가지 작업을 모두 포함해도, 전체 시간복잡도는 O(V+E)를 넘지 않는다.
  * BCC에서 접근하지 않고, 그냥 dfs spanning tree의 구조에서 바로 조건을 정리할수도 있다. 공식 해설에서는 그렇게 접근했다. 결과적으로는 같은 원리이다.

===== 코드 =====
  * 다이아몬드 이상은 코드 생략
  * Dependency: [[:ps:teflib:graph#BiconnectedComponent|teflib.graph.BiconnectedComponent]]

{{tag>BOJ ps:problems:boj:다이아몬드 5}}