結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2018-01-24 13:53:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 1,331 ms |
コンパイル使用メモリ | 163,560 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 07:08:26 |
合計ジャッジ時間 | 2,479 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> //#include <math.h> using namespace std; #define INF 1.1e9 #define LINF 1.1e18 #define FOR(i,a,b) for (int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define pb push_back #define pf push_front #define fi first #define se second #define BIT(x,n) bitset<n>(x) #define PI 3.14159265358979323846 typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> PP; //----------------------------------------------------------------------------- struct UnionFind { vector<int> data; UnionFind(int size):data(size,-1) {} bool unite(int x,int y) { x=root(x),y=root(y); if(x!=y) { if(size(x)<size(y)) swap(x,y); if(size(x)==size(y)&&root(y)<root(x)) swap(x,y); data[x]+=data[y],data[y]=x; } return x!=y; } bool same(int x,int y) { return root(x)==root(y); } int root(int x) { return data[x]<0?x:data[x]=root(data[x]); } int size(int x) { return -data[root(x)]; } }; int n,m; int main() { cin.tie(0); ios::sync_with_stdio(false); cin>>n>>m; UnionFind uf(n); REP(i,m) { int a,b;cin>>a>>b; a--,b--; uf.unite(a,b); } REP(i,n) cout<<uf.root(i)+1<<endl; return 0; }