研究者 \(i\) と利害関係にない研究者の人数を \(C_i\) とおきます。

研究者 \(i\) についての求めるべき答えはこの \(C_i\) 人の部分集合であって大きさが \(3\) のものの個数であるため、これは二項係数 \(\binom{C_i}{3}\) です。

\(\binom{C_i}{3} = \frac{1}{6} C_i(C_i - 1)(C_i - 2)\) であるため、この二項係数の値は \(C_i\) の値から \(O(1)\) 時間で計算できます。

\(C_i\) の値を求めるには、研究者 \(i\) 以外の研究者全体の人数である \(N - 1\) から研究者 \(i\) と利害関係のある研究者の人数を引けばよく、全体として \(O(N + M)\) 時間で処理できます。

実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;

int main() {
	int n, m;
	cin >> n >> m;
	vector<ll> c(n, n - 1);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		c[a - 1]--; c[b - 1]--;
	}
	rep(i, n) {
		ll ans = c[i] * (c[i] - 1) * (c[i] - 2) / 6;
		cout << ans << " \n"[i == n - 1];
	}
}