AtCoder Beginner Contest #120
問題文
省略
省略
C++に変換後のコードはこちら
int N, M, A[1d5], B[1d5];
int sz[1d5];
ll res[1d5];
{
int i, x, y;
unionFind uf;
rd(N,M,(A--,B--)(M));
uf.malloc(N);
uf.init(N);
rep(i,N) sz[i] = 1;
res[M-1] = (ll) N * (N-1) / 2;
for(i=M-1;i;i--){
res[i-1] = res[i];
x = uf(A[i]);
y = uf(B[i]);
if(uf(x,y)){
if(x != uf(x)) swap(x, y);
res[i-1] -= (ll) sz[x] * sz[y];
sz[x] += sz[y];
}
}
wtLn(res(M));
}
Current time: 2024年03月29日23時32分46秒
Last modified: 2019年07月16日01時19分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC120 ABC_D
トップページに戻る
Logged in as: unknown user (not login)