문제 링크
- http://icpc.me/15768
문제 출처
- 2018 APIO 3번
사용 알고리즘
- BCC
풀이
N개의 정점과 M개의 무향 간선으로 이루어진 그래프가 주어집니다. s에서 c를 거쳐 f로 가는 단순 경로가 존재하는 서로 다른 세 정점 s, c, f를 선택할 것입니다. 이 조건을 만족하는 (s, c, f) 순서쌍의 경우의 수를 구하는 문제입니다.
단순 경로가 아니라는 것은 반드시 두 번 이상 지나가는 정점이 존재한다는 것을 의미합니다.
반드시 두 번 이상 지나가는 정점을 v라고 한다면, 그래프에서 v를 지웠을 때 경로가 끊어지게 됩니다. 즉, v는 단절점입니다.
그러므로 s, c, f가 모두 같은 BCC에 속한다면 조건을 만족하는 단순 경로가 존재한다는 것을 알 수 있습니다.
여사건을 생각합시다.
전체 경우의 수에서 (s와 c가 다른 BCC에 있고, c와 f가 다른 BCC에 있는 경우의 수)를 빼주면 됩니다.
주어지는 그래프가 연결 그래프가 아닐 수 있으니 주의해야 합니다.