시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 859 | 272 | 141 | 30.388% |
N(1 ≤ N ≤ 100,000)개의 정점으로 이루어진 평면그래프가 있다. 이 평면그래프에 삼각형, 즉 길이가 3인 사이클이 몇 개나 존재하는지 알아내는 프로그램을 작성하시오.
평면그래프란, 열심히 노력하면 간선들이 서로 겹치지 않도록 평면상에 그릴 수 있는 그래프를 말한다.
서로 다른 세 정점 x, y, z가 있을 때, x-y, y-z, z-x의 세 간선이 존재하면 세 정점 x, y, z는 삼각형을 이루고 있다고 한다.
정점은 1번부터 N번까지 번호가 매겨져 있다.
첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상 300,000 이하의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으로 주어지지 않으며, 간선들에는 방향성이 없다.
첫째 줄에 삼각형의 개수를 출력한다.
4 6 1 2 3 1 2 3 4 2 4 1 3 4
4