31217번 - Y 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 554 | 339 | 275 | 59.013% |
문제
흐즈로는 그래프 이론을 공부하다가 흥미로운 그래프를 발견했습니다. 다음의 특징을 가지는 단순 무향 그래프를 Y라고 부릅시다.
- $4$개의 정점과 $3$개의 간선을 가집니다.
- 하나의 정점을 루트라고 부르며, 나머지 $3$개의 정점을 리프라고 부릅니다.
- $3$개의 간선은 각각의 리프와 루트를 연결합니다.
흐즈로는 Y의 성질이 매우 특이하다고 생각하여, 어떤 그래프 안에 Y가 몇 개나 존재하는지 세어 보기로 했습니다. 단순 무향 그래프에서 Y의 개수를 다음과 같이 정의합시다.
- 그래프에서 $3$개의 간선을 순서 없이 골랐을 때, 그 간선과 간선이 연결하는 정점들이 이루는 그래프가 Y가 되는 경우의 수를 그래프의 Y의 개수로 정의합니다.
단순 무향 그래프가 입력으로 주어질 때, 주어진 그래프의 Y의 개수를 출력하세요. 단, 개수가 너무 많을 수 있으니 개수를 소수 $10^9+7$로 나눈 나머지를 출력하세요.
입력
첫 번째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 분리되어 주어집니다. ($1 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2},2\times 10^5)$)
두 번째 줄부터 $m$개의 줄에 $i$번째 간선이 연결하는 정점 $u$와 $v$가 공백으로 분리되어 주어집니다. ($1 \le u,v \le n$, $u \neq v$)
주어진 그래프는 중복 간선이나 양 끝점이 같은 간선을 가지지 않음이 보장됩니다.
출력
주어진 그래프의 Y의 개수를 $10^9 + 7$로 나눈 나머지를 출력하세요.
예제 입력 1
4 6 1 2 1 3 1 4 2 3 2 4 3 4
예제 출력 1
4
그래프에서 간선 $3$개를 선택해 만들어진 부분 그래프가 Y가 되는 경우는 다음과 같습니다.
- $(1,2)$, $(1,3)$, $(1,4)$를 선택합니다.
- $(1,2)$, $(2,3)$, $(2,4)$를 선택합니다.
- $(1,3)$, $(2,3)$, $(3,4)$를 선택합니다.
- $(1,4)$, $(2,4)$, $(3,4)$를 선택합니다.
따라서 예제의 그래프의 Y의 개수는 $4$입니다. $4 \equiv 4 \pmod{10^9+7}$이므로 $4$를 출력해야 합니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호