結果
問題 | 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_back using 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; }