rt莫名其妙M了一个,求条

原题->P7299

提交记录->MLE

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;

int n,K;
int ckb[N],fa[N];
set<int> s[N];

int rt(int x){
	return (fa[x]=(fa[x]==x?x:rt(fa[x])));
}

void merge(int x,int y){
	int fx=rt(x);
	int fy=rt(y);
	if(fx==fy) return;
	fa[fx]=fy;
	s[fy].insert(s[fx].begin(),s[fx].end());
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>K;
	for(int i=1;i<=n;i++) fa[i]=ckb[i]=i,s[i].insert(i);
	for(int i=1;i<=K;i++){
		int x,y;cin>>x>>y;
		swap(ckb[x],ckb[y]);
		s[ckb[x]].insert(y);s[ckb[y]].insert(x);
	}
	for(int i=1;i<=n;i++){
		if(ckb[i]==i) continue;
		merge(i,ckb[i]);
	}
	for(int i=1;i<=n;i++){
		cout<<s[rt(i)].size()<<'\n';
	}
	return 0;
}