#195912 (C++14) No.556 仁義なきサルたち

• 問題: No.556 仁義なきサルたち
• ユーザー: dnish
• 提出日時: 2017-08-11 23:17:57
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 956 bytes
• コンパイル時間: 2,060 ms
• コンパイル使用メモリ: 173,880 KB
• 実行使用メモリ: 10,780 KB
• 最終ジャッジ日時: 2024-04-20 23:33:57
• 合計ジャッジ時間: 10,731 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 10,624 KB
testcase_01	WA	-
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	23 ms; 5,376 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	116 ms; 5,376 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-

ソースコード

#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=(n);i<(int) N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=(int) n;i--)
#define p(s) cout<<(s)<<endl
#define DEBUG(x,y) cout<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl;
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf=1e9+7;

int num[10010];
map<int,int> m;
int main(){
	int N,M;
	cin>>N>>M;
	REP(i,0,N) {
		num[i]=1;
		m[i]=i;
	}
	REP(i,0,M){
		int a,b;
		cin>>a>>b;
		a--;b--;
		if(num[m[a]]>num[m[b]]||(num[m[a]]==num[m[b]]&&m[a]<m[b])){
			num[m[a]]+=num[m[b]];
			REP(i,0,N){
				if(m[i]==m[b]){
					m[i]=m[a];
				}
			}
		}else if(num[m[a]]<num[m[b]]||(num[m[a]]==num[m[b]]&&m[a]>m[b])) {
			num[m[b]]+=num[m[a]];
			REP(i,0,N){
				if(m[i]==m[a]){
					m[i]=m[b];
				}
			}
		}
		//cout<<a+1<<": "<<m[a]+1<<" "<<b+1<<": "<<m[b]+1<<endl;
	}
	REP(i,0,N){
		while(m[m[i]]!=m[i])
		m[i]=m[m[i]];
		p(m[i]+1);
	}
	return 0;
}