并查集写法5分求调教

#include<bits/stdc++.h>
using namespace std;
long long n,q;
#define int long long
struct opra{
	char op;
	int x,y;
}arr[500100],add[500100];
struct node{
	int x,nxt,pre;
}chain[500100];
bool d[500100],nc[500100];
int fa[500100],cnt=0,ans[500100],w[500100],idx=0,head=1;
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void check(int i){
	int j=head;
	while(j!=-1){
		if(w[find(chain[j].x)]>=1){
			ans[chain[j].x]=max(ans[chain[j].x],i-1);
			if(chain[j].pre!=0){
				chain[chain[j].pre].nxt=chain[j].nxt;
				chain[chain[j].nxt].pre=chain[j].pre;
			}
			else{
				head=chain[j].nxt;
				chain[chain[j].nxt].pre=0;
			} 
		}
		j=chain[j].nxt;	
	}
	return ;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){fa[i]=i;w[i]=1;}
	for(int i=1;i<=q;i++){
		cin>>arr[i].op;
		if(arr[i].op=='D'){
			cin>>arr[i].x;
			nc[arr[i].x]=1;
			w[arr[i].x]=0;	
		}
		if(arr[i].op=='A'){
			cin>>arr[i].x>>arr[i].y;
			add[++cnt].x=arr[i].x;add[cnt].y=arr[i].y;
		}
		if(arr[i].op=='R'){
			cin>>arr[i].x;
			d[arr[i].x]=1;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(d[i]==0){
			w[find(add[i].y)]+=w[find(add[i].x)];
			fa[find(add[i].x)]=find(add[i].y);
		}
	}
	for(int i=1;i<=n;i++) if(nc[i]==0 || w[find(i)]>=1) ans[i]=q;
	for(int i=1;i<=n;i++){
		if(ans[i]==0){
			chain[idx].nxt=(idx+1);
			idx++;
			chain[idx].x=i;
			chain[idx].nxt=-1;
			chain[idx].pre=idx-1;
		}
	}
	for(int i=q;i>=1;i--){
		if(arr[i].op=='D'){
			w[fa[find(arr[i].x)]]+=1;
			if(w[fa[find(arr[i].x)]]==1) check(i);
		}
		if(arr[i].op=='R'){
			int flag=min(w[find(add[arr[i].x].x)],w[find(add[arr[i].x].y)]);
			w[find(add[arr[i].x].y)]+=w[find(add[arr[i].x].x)];
			fa[find(add[arr[i].x].x)]=find(add[arr[i].x].y);
			if(flag==0) check(i);
		}
		
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}