結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
![]() |
提出日時 | 2018-09-09 04:38:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,119 bytes |
コンパイル時間 | 1,497 ms |
コンパイル使用メモリ | 170,172 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 02:41:09 |
合計ジャッジ時間 | 2,555 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using int64 = long long; using uint64 = unsigned long long; struct uf_tree { std::vector<int> parent; int __size; uf_tree(int size_) : parent(size_, -1), __size(size_) {} void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { // size[y] > size[x] if (-parent[y] > -parent[x] or (parent[y] == parent[x] and y < x)) std::swap(x, y); parent[x] += parent[y]; parent[y] = x; __size--; } } bool is_same(int x, int y) { return find(x) == find(y); } int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); } int size(int x) { return -parent[find(x)]; } int size() { return __size; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, M; cin >> N >> M; uf_tree uf(N); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; uf.unite(a, b); } for (int i = 0; i < N; i++) { cout << uf.find(i) + 1 << endl; } return 0; }