P1196 [NOI2002]银河英雄传说

洛谷题目

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 50005

using namespace std;

int f[MAXN];
int rank1[MAXN];
int sum[MAXN];

void init(void) {
	for (int i = 0; i < MAXN; i++)
		f[i] = i;
	memset(rank1, 0, sizeof(rank1));
	fill(sum, sum + MAXN, 1);
}

int find(int x) {
	if (x != f[x]) {
		int r1 = find(f[x]);
		rank1[x] += rank1[f[x]];
		f[x] = r1;
	}
	return f[x];
}

void insert(int x, int y) {
	int r1 = find(x);
	int r2 = find(y);
	rank1[r1] += sum[r2];
	sum[r2] += sum[r1];
	f[r1] = r2;
	sum[r1] = 0;//
}

int main()
{
	//freopen("data.txt", "r", stdin);
	
	init();

	int N = 30000;
	int K;
	cin >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		char c;
		scanf(" %c%d%d", &c, &a, &b);
		if (c == 'M')
			insert(a, b);
		else {
			if (find(a) != find(b))
				cout << -1 << endl;
			else
				cout << abs(rank1[a] - rank1[b]) - 1 << endl;
		}
	}
	
	
	//freopen("CON", "r", stdin);
	system("pause");
	return 0;
}