結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
|
提出日時 | 2020-02-26 16:09:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 912 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 168,696 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-13 15:24:09 |
合計ジャッジ時間 | 2,406 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int nmax=10005; int par[nmax],siz[nmax]; void init(int x){ for(int i=0;i<x;i++){ par[i]=i; siz[i]=1; } } int root(int x){ if(par[x]==x){ return x; } return par[x]=root(par[x]); } void unite(int x,int y){ x=root(x); y=root(y); if(x==y){ return ; } par[y]=x; siz[x]+=siz[y]; } int main(){ int n,m;cin >> n >> m; init(n); for(int i=0;i<m;i++){ int a,b;cin >> a >> b; a--,b--; if(siz[root(a)]>siz[root(b)]){ unite(a,b); } else if(siz[root(a)]<siz[root(b)]){ unite(b,a); } else{ if(root(a)<root(b)){ unite(a,b); } else{ unite(b,a); } } } for(int i=0;i<n;i++){ cout << root(i)+1 << endl; } }