結果

問題 No.556 仁義なきサルたち
ユーザー ciel
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
}
0