2264934_ac_388ms_388k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#define MAX 30001

int a[MAX], b[MAX], c[MAX];

void solve(int n)
{
	int t, T, tmp, Tmp;
	int a1, b1;
	int a2, b2;
	
	T = t = n;tmp = 0;
	while(a[n]!=n)
	{
		tmp += b[n];
		n = a[n];
	}
	Tmp = tmp;
	b1 = b[t];a1 = a[t];
	while(a[t]!=t)
	{
		t = a1;
		a2 = a[a1];b2 = b[a1];
		a[a1] = n;
		b[a1] = tmp-b1;
		tmp -= b1;
		b1 = b2;
		a1 = a2;
	}
	a[T] = n;b[T] = Tmp;
}

int main()
{
	char com[2];
	int R1, R2;
	long l, p;
	int i, j;
	
	scanf("%ld",&p);
	for(l = 0; l < MAX; l++)
		a[l] = l, b[l] = 0, c[l] = 1;
	for(l = 0; l < p; l++)
	{
		scanf("%s",com);
		if(com[0]=='M')
		{
			scanf("%d%d",&i,&j);
			solve(i);
			solve(j);
			R1 = a[j];R2 = a[i];
			a[R1] = R2;
			b[R1] = c[R2];
			c[R2] += c[R1];
		}
		else
		{
			scanf("%d",&i);
			solve(i);
			R1 = a[i];
			printf("%d\n",c[R1]-b[i]-1);
			
		}
	}
	return 1;
}