[BOJ] 1762번: 평면그래프와 삼각형

https://www.acmicpc.net/problem/1762

임의의 평면 그래프에서 특정 graph의 갯수를 세는 문제는 O(N)입니다. (논문 : http://jgaa.info/accepted/99/Eppstein99.3.3.pdf) 그러나 해당 논문은 잘 이해가 가지 않고, 대신 생각한 방법은 모든 간선(점 u와 v를 잇는 선이라고 가정)에 대해 u,v와 공통적으로 연결된 선분의 갯수를 $deg(U)lg(deg(V))$에 찾는 것입니다. degree가 더 큰 것을 log로 취하게끔 하면 되겠네요. 이 때 degree가 크면 어떡하냐 싶을 수 있지만 평면그래프이기 때문에 $ E <= 3V-6 $이라 degree의 총 합은 $6V - 12$ 이하로 굉장히 작기 때문에 일반적인 그래프일 때 $M^1.5$임을 감안하면 시간복잡도는 그다지 크지 않습니다. 엄밀한 증명은 다음 기회에..ㅎㅎㅎ...

https://github.com/blisstoner/BOJ/blob/master/1762.cpp