結果
問題 | No.556 仁義なきサルたち |
ユーザー |
|
提出日時 | 2017-08-11 22:43:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 1,373 bytes |
コンパイル時間 | 1,863 ms |
コンパイル使用メモリ | 169,004 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 21:27:40 |
合計ジャッジ時間 | 2,529 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Union_Find {//各要素が属する集合の代表(根)を管理する//もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しいvector<int> data;Union_Find(int size) : data(size, -1) {}bool Union(int x, int y) {x = Find(x);y = Find(y);bool is_union = (x != y);if (is_union) {if (data[x] > data[y] || (data[x] == data[y] && x > y)) swap(x, y);data[x] += data[y];data[y] = x;}return is_union;}int Find(int x) {if (data[x] < 0) { //要素xが根であるreturn x;} else {data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新されるreturn data[x];}}bool same(int x, int y) {return Find(x) == Find(y);}int size(int x) {return -data[Find(x)];}};int main() {cin.tie(0);ios::sync_with_stdio(false);int n, m;cin >> n >> m;Union_Find uf(n);for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;a--;b--;uf.Union(a, b);}for (int i = 0; i < n; i++) {int root = uf.Find(i);cout << (root < 0 ? i + 1 : root + 1) << endl;}return 0;}