사용자 도구

사이트 도구


ps:problems:boj:31217

Y

ps
링크acmicpc.net/…
출처BOJ
문제 번호31217
문제명Y
레벨실버 3
분류

그래프

시간복잡도O(V+E)
인풋사이즈V<=10^5, E<=2*10^5
사용한 언어Python 3.11
제출기록34024KB / 228ms
최고기록208ms
해결날짜2024/01/08

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
V R L U O
 
ps/problems/boj/31217.txt · 마지막으로 수정됨: 2024/01/08 12:18 저자 teferi