Split the SSHS 2

Boomerangs과 매우 비슷한 문제이다. 사실 Boomerangs 보다 이 문제가 더 어려워보이는데, 난이도는 더 쉽게 매겨져있다..

정점 세 개를 골라 그 정점들을 연결하는 엣지들을 지우는 것이므로, 엣지는 최소 0개에서 최대 3개까지 지워질수 있다. 정점 세개 간에 엣지가 하나도 없다면 지워봤자 바뀌는 것이 없으므로 신경쓰지 않아도 된다. 그러므로 지워야 하는 엣지들을 두 정점 사이의 엣지 1개와, 두 정점들과 세번째 정점 사이의 엣지들 0~2개라고 생각해도 된다.

두 정점 사이의 엣지가 단절선이라면, 세번째 정점에 관계 없이 그래프가 분리된다. Boomerangs과 똑같다. 단절선 하나를 잡으면, 세번째 점은 N-2 개중에서 아무거나 고르면 되니까, 이러한 형태의 개수는 {단절선의 개수} * (N-2) 가 된다. 여기에서 중복 카운팅을 제거해야 하는데, (u,v,w)에 대해서 u-v가 단절선이고, v-w가 단절선인 경우의 개수를 세어주면 된다. u-v,v-w,w-u 가 모두 단절선이 되는 경우는 존재하지 않으므로 생각하지 않아도 된다.

이제, u,v,w 사이의 엣지들 중에서 단절선이 없는 경우를 세어주면 된다. 이것도 Boomerangs과 마찬가지이다. u,v,w가 같은 BCC안에 있고, u-v-w 형태로 엣지가 있고, 그 BCC 안에서 v와 연결된 다른 노드가 없으면, u,v,w 이 답이 된다. BCC 마다 그 BCC안에 해당되는 노드와 엣지들만으로 그래프를 그려서 각 노드들의 차수를 구한다음에, 차수가 2인 노드 (v의 역할)을 찾아주면 된다. Boomerangs과 다른 점은 여기에서도 중복 카운팅이 생길수 있다는 점이다. (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: teflib.graph.BiconnectedComponent