結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
|
提出日時 | 2018-09-04 19:04:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,100 bytes |
コンパイル時間 | 1,857 ms |
コンパイル使用メモリ | 171,736 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 12:55:02 |
合計ジャッジ時間 | 2,858 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,j,n) for(int i=(j);i<(n);i++) #define erep(i,j,n) for(int i=(j);i<=(n);i++) #define all(i) i.begin(),i.end() #define rall(i) i.rbegin(),i.rend() #define INF 1e9 const int mod = 1e9+7; typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int, int> pi; typedef long long i64; struct UnionFind { vector<int> node; UnionFind(int sz) { node.resize(sz, -1); } int root(int x) { return (node[x] < 0 ? x : node[x] = root(node[x])); } int size(int x) { return -node[root(x)]; } void unite(int x, int y) { x = root(x); y = root(y); if(x == y) return; if(size(x) < size(y)) { swap(x, y); } else if(size(x) > size(y)) { } else if(x > y) { swap(x, y); } node[x] += node[y]; node[y] = x; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m; cin >> n >> m; UnionFind uf(n + 1); rep(i, 0, m) { int a, b; cin >> a >> b; uf.unite(a, b); } erep(i, 1, n) cout << uf.root(i) << endl; }