yukicoder No.556 仁義なきサルたち

Union-Findするだけ

int uniroot[10010],unicnt[10010];
void ufinit(int n){for(int i=0;i<n;i++){uniroot[i]=i;unicnt[i]=1;}}
int root(int x){return uniroot[x]!=x?uniroot[x]=root(uniroot[x]):x;}
void uni(int x,int y){if((x=root(x))==(y=root(y)))return;uniroot[x]=y;unicnt[y]+=unicnt[x];}

n,m,a,b;
main(){
	scanf("%d%d",&n,&m);
	ufinit(n+1);
	while(m--){
		scanf("%d%d",&a,&b);
		a=root(a);
		b=root(b);
		if(a!=b){
			if(unicnt[a]<unicnt[b]||unicnt[a]==unicnt[b]&&a>b)a^=b^=a^=b;
			uni(b,a);
		}
	}
	for(int i=1;i<=n;i++)printf("%d\n",root(i));
}

順番に縮めよう
あきらかにufinitとuni関数はいらない

r['~~'],c['~~'];
t(x){return r[x]-x?r[x]=t(r[x]):x;}

n,a,b,i,j;
main(){
	for(scanf("%d%*d",&n);i++<n;c[i]=1)r[i]=i;
	for(;~scanf("%d%d",&a,&b);a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a,c[a]+=c[b]:0)a=t(a),b=t(b);
	for(;j++<n;)printf("%d\n",t(j));
}

1つ目のfor文に登場するnは1e4に置き換えて良いので、2つあるscanfをまとめることができる

//before
for(scanf("%d%*d",&n);i++<n;c[i]=1)r[i]=i;
for(;~scanf("%d%d",&a,&b);a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a;c[a]+=c[b]:0)a=t(a),b=t(b);
//after
for(;i++<1e4;c[i]=1)r[i]=i;
for(;~scanf("%d%d",&a,&b);--x?a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a;c[a]+=c[b]:0:(n=a))a=t(a),b=t(b);
//ただしxはmain第一引数とする

あとは3つあるfor文を1つにまとめる

for(;i++<1e4;c[i]=1)r[i]=i;for(;~scanf("%d%d",&a,&b);--x?a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a,c[a]+=c[b]:0:(n=a))a=t(a),b=t(b);for(;j++<n;)printf("%d\n",t(j));
for(;i++<1e4?c[i]=1,r[i]=i:~scanf("%d%d",&a,&b)?a=t(a),b=t(b),--x?a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a,c[a]+=c[b]:1:(n=a):j++<n&&printf("%d\n",t(j)););

ということでまとめるとこう

r['~~'],c['~~'];
i,j,a,b,n;
t(k){return r[k]-k?r[k]=t(r[k]):k;}
main(x){for(;i++<1e4?c[i]=1,r[i]=i:~scanf("%d%d",&a,&b)?a=t(a),b=t(b),--x?a-b?c[a]<c[b]|c[a]==c[b]&a>b?a^=b^=a^=b:0,r[b]=a,c[a]+=c[b]:1:(n=a):j++<n&&printf("%d\n",t(j)););}

233B
return文省略は上手くいかず

メモ

yukicoderでゆるふわgolf

yukicoder No.556 仁義なきサルたち