연결된 엣지쌍들 ((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의 구조에서 백엣지의 갯수와 등등을 이용해서 조건을 정리하고 그것을 기준으로 계산할 수도 있겠지만, 결국은 비슷한 원리이므로 이해가 편한식으로 추상화시키면 될듯 하다.