[Python] 31217번 Y

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

31217번: Y

---

 

24/01/09

 

 

간단한 차 수열+조합론 문제이다.

 

좋은 문제라고 생각된다.

---

 

문제 접근 방식:

 

 

Y 그래프의 중심이 되는 루트를 각각의 정점마다 생각해보자.

 

즉, 우리는 $1, 2, \cdots, N$번 정점까지 있을 때, $i$번 정점이 Y 그래프의 루트가 되는 경우를 $1$번 정점부터 $N$번 정점까지 모두 더하여 최종 답을 구하면 된다.

 

$i$번 정점에 $3$개 이상의 간선이 연결되어 있는 경우에만 Y 그래프를 만들 수 있다.

 

만약 $i$번 정점에 $3$개 이상의 간선이 연결되어 있는 경우, 우리는 그 정점을 루트로 하여 Y 그래프를 형성할 수 있다.

 

그 개수는 $ \sideset{_{(i \textrm{ 번 정점에 연결된 간선의 개수)}} } {_3} C$이다.

 

즉, $i \textrm{ 번 정점에 연결된 간선의 개수}$를 $E$라고 한다면, 그 개수는 $\frac{E(E-1)(E-2)}{6}$이다.

 

$\mathrm{MOD}=10^9+7$에 대한 $6$의 모듈로 역원은 $166 \ 666 \ 668$이므로, $\mathrm{MOD}$로 나눈 나머지 값을 계산할 때 이를 활용하면 충분하다.

 

또한, 어떤 정점에 연결돼있는 간선의 개수만 세주면 충분하므로, 차수열을 구현하면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 31217번 Y
# 그래프 이론, 조합론
'''
접근 방법:
Y 그래프의 중심이 되는 루트를 모든 정점마다 생각해보자.
만약 어떤 정점에 3개 이상의 간선이 연결되어 있다면,
우리는 그 정점을 중심으로 Y그래프를 형성할 수 있다.
그 개수는 (그 정점에 연결된 간선의 개수)C3이다.
즉, (정점에 연결된 간선 개수) = E라고 한다면,
E*(E-1)*(E-2)//6.
6의 모듈로 역원은 166666668
따라서 어떤 정점에 연결되있는 간선의 개수만 세주면 된다.
'''
import sys
input = sys.stdin.readline
MOD = 1_000_000_000 + 7
MOD_inv_of_6 = 166_666_668

N, M = map(int, input().rstrip().split())
number_of_edges = [0 for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().rstrip().split())
    number_of_edges[u] += 1
    number_of_edges[v] += 1
answer = 0
for i in range(1, N+1):
    if number_of_edges[i] >= 3:
        E = number_of_edges[i]
        number_of_Y = (E*(E-1)*(E-2)*MOD_inv_of_6)
        number_of_Y %= MOD
        answer += number_of_Y
        answer %= MOD
print(answer)