結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 22:45:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 921 ms |
コンパイル使用メモリ | 98,584 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 21:30:19 |
合計ジャッジ時間 | 1,879 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<iostream>#include<iomanip>#include<math.h>#include<vector>#include<algorithm>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<complex>#define INF (long long)1000000000#define MOD 1000000007#define EPS 1e-8#define REP(i, m) for(long long i = 0; i < m; ++i)#define FOR(i, n, m) for(long long i = n; i < m; ++i)#define ALL(v) v.begin(), v.end()#define pb push_backusing namespace std;typedef long long ll;typedef pair<ll, ll> P;typedef long double ld;class union_find {public:union_find(int n): par_(n, -1){}void init(int n) {par_.assign(n, -1);}int root(int x) {return par_[x] < 0 ? x : par_[x] = root(par_[x]);}bool unite(int x, int y) {x = root(x); y = root(y);if(x == y) {return false;} else {par_[x] += par_[y];par_[y] = x;return true;}}bool same(int x, int y) {return root(x) == root(y);}int size(int x) {return -par_[root(x)];}private:std::vector<int> par_;};int main() {int n,m;cin>>n>>m;union_find uf(n);REP(i,m) {int a, b;cin>>a>>b;--a;--b;if(uf.same(a,b)) continue;if(uf.size(a)>uf.size(b)) {uf.unite(a,b);} else if(uf.size(b)>uf.size(a)) {uf.unite(b,a);} else {if(uf.root(a)<uf.root(b)) uf.unite(a,b);else uf.unite(b,a);}}REP(i,n) cout<<uf.root(i)+1<<endl;}