====== Boomerangs ======

===== 풀이 =====
  * 연결된 엣지쌍들 %%((u-v), (v-w))%% 중에서 그 엣지 두개를 제거했을때 그래프를 분리시킬 수 있는 것의 갯수를 구하라는 문제.
  * 일단 엣지 하나가 단절선이라면 당연히 가능하다. 단절선에 해당하는 엣지 하나만 제거해도 그래프가 분리되기 때문이다. 이것을 세는것은, 각  단절선마다 단절선에 연결된 엣지의 수를 모두 더해준 다음에, 중복으로 카운트 된 단절선 두개가 붙어있는 쌍의 갯수를 빼주면 된다.
  * 엣지가 둘다 단절선이 아니지만 조건을 만족시키는 경우는, u-v-w 모양의 부메랑을 제거했더니 v가 u와 w를 포함하는 컴포넌트로부터 분리되는 경우이다. 이것이 되는 조건은, u,v,w가 모두 같은 BCC 안에 있고, v는 u와 w외에 그 BCC 안에서 연결된 노드가 없어야 한다. 다른 BCC에 연결된 노드는 있어도 된다는 점에 주의하자. 이것때문에 단순히 전체 그래프안에서의 차수를 확인해서는 안되고, BCC단위로 분리된 그래프에서 차수를 다시 계산해줘야 한다.
  * 이 두 경우에 해당하는 엣지쌍의 갯수를 각각 구해서 더해주면 된다. 실제 필요한 작업은 엣지단위로 BCC를 분리하고, 각 BCC에서 차수를 찾고, 단절선을 구하고, 단절선끼리 연결된 페어의 갯수를 찾는 정도의 작업들이 필요하지만, BCC를 O(V+E)에 분리해놓고 나면 나머지 작업들은 간단하게 처리된다.
  * BCC에서 접근하지 않고, 그냥 dfs spanning tree의 구조에서 백엣지의 갯수와 등등을 이용해서 조건을 정리하고 그것을 기준으로 계산할 수도 있겠지만, 결국은 비슷한 원리이므로 이해가 편한식으로 추상화시키면 될듯 하다.

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

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