Atcoder解いてみた AtCoder Beginner Contest C - Peer Review

AtCoder Beginner Contest C - Peer Review

問題はこちら

回答

無効グラフを活用

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N;
int M;

std::vector<int> A;
std::vector<int> B;

std::vector<std::vector<int>> C;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M;
	A.resize(M);
	B.resize(M);

	C.resize(N);

	for (int i = 0; i < M; i++) {
		int A;
		int B;
		std::cin >> A >> B;
		A--;
		B--;

		C[A].push_back(B);
		C[B].push_back(A);
	}

	for (int i = 0; i < N; i++) {
		long long corNum = static_cast<long long>(C[i].size());
		long long notCorNum = static_cast<long long>(N - corNum - 1);

		long long ans = 0;
		if (notCorNum >= 3) {
			ans = (notCorNum  * (notCorNum - 1) * (notCorNum - 2)) / (3 * 2 * 1);
		}
		std::cout << ans << " ";
	}

	return 0;
}