Submission #5119798

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
private:
	vector<long long> par;
public:
	UnionFind(int N) { par = vector<long long>(N, -1LL); }
	int find(int x);
	long long size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};
//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

long long UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	//既に同じ集合に属しているならば繋げない
	if (same(x,y)) return;

	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}

int main() {
	long long n,m;
	cin >> n >> m;
	long long ans[m+1];
	long long A[m],B[m];
	UnionFind uf(n);

	for (int i = 0;i < m;i++) {
		cin >> A[i] >> B[i];
	}

	ans[m] = n * (n - 1) / 2;
	for (int i = m - 1;i >= 0;i--) {
		if (!uf.same(A[i]-1,B[i]-1)) {
			ans[i] = ans[i+1] - uf.size(A[i]-1) * uf.size(B[i]-1);
		} else {
			ans[i] = ans[i+1];
		}
		uf.unite(A[i]-1,B[i]-1);
	}

	for(int i = 1;i < m + 1;i++) {
		cout << ans[i] << endl;
	}
}

Submission Info

Judge Result