結果
問題 | No.556 仁義なきサルたち |
ユーザー |
|
提出日時 | 2020-05-29 19:33:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,180 bytes |
コンパイル時間 | 854 ms |
コンパイル使用メモリ | 76,920 KB |
最終ジャッジ日時 | 2025-01-10 16:17:06 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <numeric> #include <vector> struct UnionFind { std::vector<int> par, sz; int gnum; explicit UnionFind(int n) : par(n), sz(n, 1), gnum(n) { std::iota(par.begin(), par.end(), 0); } int find(int v) { return (par[v] == v) ? v : (par[v] = find(par[v])); } void unite(int u, int v) { u = find(u), v = find(v); if (u == v) return; sz[u] += sz[v]; par[v] = u; --gnum; } bool same(int u, int v) { return find(u) == find(v); } bool ispar(int v) { return v == find(v); } int size(int v) { return sz[find(v)]; } }; void solve() { int n, m; std::cin >> n >> m; UnionFind uf(n); while (m--) { int u, v; std::cin >> u >> v; --u, --v; if (uf.size(v) > uf.size(u) || (uf.size(v) == uf.size(u) && uf.find(v) < uf.find(u))) { std::swap(u, v); } uf.unite(u, v); } for (int v = 0; v < n; ++v) { std::cout << uf.find(v) + 1 << "\n"; } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }