問題はこちら
No.556 仁義なきサルたち - yukicoder
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文省略は上手くいかず