結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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>ysz[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;}