結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
|
提出日時 | 2019-08-29 17:52:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,096 bytes |
コンパイル時間 | 2,261 ms |
コンパイル使用メモリ | 199,412 KB |
最終ジャッジ日時 | 2025-01-07 15:34:50 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; class UF { private: vector<int> par,c; public: UF(int n) { for (int i=0;i<n;i++) par.push_back(i); c.resize(n,1); } int find(int a) { if (par[a]==a) return a; return par[a]=find(par[a]); } void unite(int a,int b) { int x=find(a); int y=find(b); if (x==y) return; par[y]=x; c[x]+=c[y]; } int cnt(int a) { return c[a]; } }; int main() { int n,m; cin>>n>>m; UF uf(n); while (m--) { int a,b; cin>>a>>b; a--,b--; int x=uf.find(a); int y=uf.find(b); if (x==y) continue; if (uf.cnt(x)>uf.cnt(y)) uf.unite(x,y); else if (uf.cnt(x)<uf.cnt(y)) uf.unite(y,x); else { if (x<y) uf.unite(x,y); else uf.unite(y,x); } } for (int i=0;i<n;i++) cout<<uf.find(i)+1<<endl; return 0; }