Codeforces 229C (142C) Triangles

問題

n頂点m辺からなる無向グラフが与えられる。

n頂点からなる完全グラフのうち、m辺をAliceが、
のこりの辺をBobが取る。

Aliceのグラフ中の三角形の数と、
Bobのグラフ中の三角形の数の和を求めよ。

制約条件

n, m≦10^6

方針

Aliceの辺1本とBobの辺2本を使った三角形と、
Bobの辺1本とAliceの辺2本を使った三角形の数の合計を求め、
完全グラフの三角形の数から引けば、求める三角形の個数になる。

それはどうやって求めればよいかと言うと、
それぞれの頂点の次数をd[i]とすると、
Σd[i] * (n - 1 - d[i])は、ちょうど引く三角形の個数の2倍になっている。
（全ての引くべき三角形を2回ずつ数えているので）

ソースコード

const int MX = 1000010;
int n, m;
int deg[MX];

int main(){
	scanf("%d%d", &n, &m);
	rep(i, m){
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;
		deg[a]++; deg[b]++;
	}
	ll tot = n * (n - 1ll) * (n - 2) / 6;
	ll bad = 0;
	rep(i, n){
		bad += deg[i] * (n - 1 - deg[i]);
	}
	cout << tot - bad / 2 << endl;
	return 0;
}