結果

問題 No.556 仁義なきサルたち
コンテスト
ユーザー 梧桐
提出日時 2026-01-25 09:26:42
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 907 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,422 ms
コンパイル使用メモリ 184,100 KB
実行使用メモリ 16,204 KB
最終ジャッジ日時 2026-01-25 09:26:48
合計ジャッジ時間 5,428 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 3 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
struct P{
	int value;
	int dad;
	int num;
}a[10005];
int find(int x){
	if(a[x].dad==-1) return x;
	else return find(a[x].dad);
}
int main(){
//	freopen("monkey.in","r",stdin);
//	freopen("monkey.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		a[i].value=i;
		a[i].dad=-1;
		a[i].num=0;
	}
	for(int i=1;i<=m;++i){
		int p,q;
		cin>>p>>q;
		if(a[p].dad!=-1)
		p=a[p].dad;
		if(a[q].dad!=-1)
		q=a[q].dad; 
		if(p==q) continue;
		if(a[p].num>a[q].num){
			a[p].num+=a[q].num;
			a[q].dad=p;
			a[p].num++;
		}
		if(a[p].num==a[q].num){
			if(p>q){
			a[q].num+=(a[p].num+1);
			a[p].dad=q;
			}
			if(p<q){
			a[p].num+=a[q].num;
			a[q].dad=p;
			a[p].num++;
			}
		}
		if(a[p].num<a[q].num){
			a[q].num+=(a[p].num+1);
			a[p].dad=q;
		}
	}
	for(int i=1;i<=n;++i){
		if(a[i].dad==-1) cout<<i;
		else cout<<find(i);
		cout<<endl; 
	}
	return 0;
}
0