1642.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 62 行

/*  This Code is Submitted by wywcgs for Problem 1642 on 2006-01-20 at 01:21:17 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 25600;
typedef pair<int, int> pii;

class UFSet {
private:
	int parent[MAX], rank[MAX];
public:
	void make();
	pii find(int);
	void unionSet(int, int, int);
	int dis(int);
};
void UFSet::make() {
	memset(parent, -1, sizeof(parent));
	memset(rank, 0, sizeof(rank));
}
pii UFSet::find(int x) {
	if(parent[x] == -1) return pii(x, 0);
	else {
		pii p = find(parent[x]);
		parent[x] = p.first; rank[x] += p.second;
		return pii(parent[x], rank[x]);
	}
}
void UFSet::unionSet(int x, int y, int l) {
	pii X = find(x), Y = find(y);
	if(X.first != Y.first) parent[X.first] = y, rank[X.first] = l;
}
int UFSet::dis(int x) {
	return find(x).second;
}

int main()
{
	UFSet ufs;
	int t, T;
	char o;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%*d");
		ufs.make();
		while(scanf("\n%c", &o) != EOF && o != 'O') {
			int x, y;
			if(o == 'E') {
				scanf("%d", &x);
				printf("%d\n", ufs.dis(x));
			} else {
				scanf("%d %d", &x, &y);
				ufs.unionSet(x, y, abs(x-y)%1000);
			}
		}
	}
	
	return 0;
}