테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Y ======

===== 풀이 =====
  * 루트 노드를 하나 정하고, 루트와 인접한 노드 3개를 고르면 Y 한개를 만들수 있다. 그러므로, u를 루트로 하는 Y의 개수는 Y와 인접한 노드들 중에서 3개를 뽑는 경우의 수와 같다. C(deg(u), 3)을 O(1)에 계산하면 된다.
  * 처음에 O(E)로 그래프를 읽으면서 각 노드의 차수들을 계산해놓는다면, 각 노드에 대해서 그 노드를 루트로 하는 Y의 개수를 구하는 것은 모두 O(V)에 처리된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31217. Y".

- Problem link: https://www.acmicpc.net/problem/31217
- Solution link: http://www.teferi.net/ps/problems/boj/31217

Tags: [graph]
"""

import math
import sys

MOD = 10**9 + 7


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    degrees = [0] * n
    for _ in range(m):
        u, v = [int(x) - 1 for x in sys.stdin.readline().split()]
        degrees[u] += 1
        degrees[v] += 1

    answer = sum(math.comb(d, 3) for d in degrees) % MOD
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:실버_3}}