Y (백준 31217)

안녕하세요. 오늘은 개수를 셀 거예요.

문제

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

아이디어

일단 Y의 중심을 중심점이라고 합시다.
중심점을 임의의 정점 i로 고정하면 만들 수 있는 Y의 개수가 정해집니다.
i와 연결된 정점의 개수를 x라고 하면 x<=2인 경우 0, x>=3인 경우 xC3이 됩니다. 이 값을 구해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, M, i, cnt[101010] = { 0 }, a, b;
    cin >> N >> M;
    for (i = 0; i < M; i++)
    {
        cin >> a >> b;
        cnt[a]++; cnt[b]++;
    }

    ll ans = 0;
    for (i = 1; i <= N; i++)
    {
        if (cnt[i] <= 2) continue;
        ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
        ans %= 1000000007;
    }
    cout << ans;
}

감사합니다.