結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 22:46:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,541 bytes |
コンパイル時間 | 833 ms |
コンパイル使用メモリ | 99,604 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 21:30:49 |
合計ジャッジ時間 | 1,686 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<sstream>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<cmath>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<numeric>#include<functional>#include<algorithm>#include<bitset>#include<tuple>#include<unordered_set>#include<random>#include<array>#include<cassert>using namespace std;#define INF (1<<29)#define rep(i,n) for(int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()#define uniq(v) v.erase(unique(all(v)),v.end())#define MOD 1000000007class UnionFind{vector<int> par;vector<int> _size;public:UnionFind(int max_n) :par(max_n), _size(max_n){}void init(int n){for (int i = 0; i<n; i++){par[i] = i;_size[i] = 1;}}int find(int x){if (par[x] == x)return x;return par[x] = find(par[x]);}void unite(int x, int y){x = find(x);y = find(y);par[y] = x;_size[x] += _size[y];}bool same(int x, int y){return find(x) == find(y);}int size(int x){return _size[find(x)];}};int main() {ios::sync_with_stdio(0);cin.tie(0);int n,m;cin>>n>>m;UnionFind uf(n);uf.init(n);rep(i,m){int a,b;cin>>a>>b;a--;b--;int sa,sb;a = uf.find(a);b = uf.find(b);if (a==b)continue;sa = uf.size(a);sb = uf.size(b);if (sa < sb){uf.unite(b,a);}else if (sa > sb){uf.unite(a, b);}else{uf.unite(min(a,b), max(a,b));}}rep(i,n){cout << uf.find(i)+1<<endl;}return 0;}