結果

問題 No.556 仁義なきサルたち
ユーザー ikdikd
提出日時 2017-08-11 23:47:16
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 875 bytes
コンパイル時間 602 ms
コンパイル使用メモリ 63,480 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 22:09:33
合計ジャッジ時間 1,441 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
using namespace std;
#define repeat(i,n) for(int i=0;i<(n);i++)
struct UF{
int n;
vector<int> pr, sz;
UF(int n_){
n=n_;
pr.resize(n);
repeat(i, n) pr[i]=i;
sz.resize(n, 1);
}
int fi(int x){
if(x==pr[x]) return pr[x];
else return pr[x]=fi(pr[x]);
}
void mg(int x, int y){
x=fi(x);
y=fi(y);
if(x==y) return;
if(sz[x]==sz[y]){
sz[min(x, y)]+=sz[max(x, y)];
pr[max(x, y)]=min(x, y);
}else{
if(sz[x]<sz[y]) swap(x, y); // x>y
sz[x]+=sz[y];
pr[y]=x;
}
}
};
int main(){
int n, m;
cin>> n>> m;
vector<int> a(m), b(m);
repeat(i, m) cin>> a[i]>> b[i];
UF uf(n);
repeat(i, m){
uf.mg(a[i]-1, b[i]-1);
}
repeat(i, n){
cout<< uf.fi(i)+1<< endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0