結果
問題 | No.556 仁義なきサルたち |
ユーザー |
|
提出日時 | 2017-08-12 01:56:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 759 bytes |
コンパイル時間 | 662 ms |
コンパイル使用メモリ | 69,228 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 22:54:32 |
合計ジャッジ時間 | 1,489 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> using namespace std; class union_find{ int *parent,*s,n; public: int root(int a){return parent[a]==a?a:(parent[a]=root(parent[a]));} union_find(int _n){n=_n;parent=new int[n];s=new int[n];for(int i=0;i<n;i++)parent[i]=i,s[i]=1;} ~union_find(){delete []parent;delete []s;} int same(int a,int b){return root(a)==root(b);} int unite(int a,int b){ int x=root(a),y=root(b);if(x==y)return 0; if(s[x]>s[y] || (s[x]==s[y]&&x<y)){ parent[y]=x; s[x]+=s[y]; }else{ parent[x]=y; s[y]+=s[x]; } return 1; } }; int main(){ int n,m,a,b; scanf("%d%d",&n,&m); union_find uf(n); for(int i=0;i<m;i++)scanf("%d%d",&a,&b),uf.unite(a-1,b-1); for(int i=0;i<n;i++)printf("%d\n",uf.root(i)+1); }