평면 그래프의 삼각형 개수
시간 제한2초메모리 제한128 MB
정점 최대 10만 개, 간선 최대 30만 개인 평면 그래프에서 삼각형(길이 3 사이클) 개수를 효율적으로 세는 문제입니다.
문제
N개의 정점으로 이루어진 평면 그래프가 주어진다. 여기서 1 <= N <= 100,000이다. 이 그래프 안에 삼각형, 즉 길이가 3인 사이클이 몇 개 있는지 구하는 프로그램을 작성하시오.
평면 그래프는 간선이 서로 교차하지 않도록 평면에 그릴 수 있는 그래프이다.
서로 다른 세 정점 x, y, z에 대해 간선 x-y, y-z, z-x가 모두 존재하면, 이 세 정점은 하나의 삼각형을 이룬다.
정점은 1번부터 N번까지 번호가 매겨져 있다.
입력
첫째 줄에 두 정수 N과 M이 주어진다. M은 간선의 개수이며 0 <= M <= 300,000을 만족한다.
다음 M개의 줄에는 각 간선이 잇는 서로 다른 두 정점의 번호가 주어진다. 같은 간선은 중복해서 주어지지 않으며, 모든 간선은 무방향이다.
출력
첫째 줄에 삼각형의 개수를 출력한다.