本文共 1600 字，大约阅读时间需要 5 分钟。

银河英雄传说

题目链接： /

题目大意

有一些点，每次你可以把一个点所在的链的前头接在另一个点所在的链的后头上。

思路

那这一题问是否连通，我们自然会想到并查集。

但是它有一个东西就是要问你一个连通的链中两个点之间的距离。

就不如在这道题中，我们弄两个值，一个是它到它最后的父亲的位置，一个是它这个连通块的距离。

那我们可以维护一下，那我们要维护到连通块父亲的距离，要怎么弄。

所以我们就要维护连通块的大小，在 find 操作的时候就直接等于（因为你这样找到的都是在同一个连通块里面）。在 connect 操作里面就是原来两个连通块大小的和。

那就可以了。

代码

#include
   
    using namespace std;int T, fa[30001], x, y;int num[30001], dis[30001];char c;int abss(int now) {   //求绝对值	if (now < 0) return -now;	return now;}int find(int now) {   //并查集操作	if (fa[now] == now) return now;		else {    			int tmp = fa[now];			fa[now] = find(fa[now]);			dis[now] += dis[tmp];//距离像统计前缀和一样加上			num[now] = num[tmp];//个数就直接等于（因为是同一个连通块）			return fa[now];		}}void connect(int x, int y) {   	int X = find(x), Y = find(y);	fa[X] = Y;	dis[X] = dis[Y] + num[Y];//接在后面的距离变成接在前面的距离加上前面的长度	num[Y] += num[X];//个数就是两个加起来}int main() {   	for (int i = 1; i <= 30000; i++) {   //初始化		fa[i] = i;		num[i] = 1;	}		scanf("%d", &T);	for (int times = 1; times <= T; times++) {   		c = getchar();		while (c != 'M' && c != 'C') c = getchar();				if (c == 'M') {   			scanf("%d %d", &x, &y);			connect(x, y);		}		else {   			scanf("%d %d", &x, &y);			int X = find(x), Y = find(y);			if (X != Y) printf("-1\n");				else {   					printf("%d\n", abss(dis[x] - dis[y]) - 1);//问的不是边的数量而是中间点的数量，所以要减一				}		}	}		return 0;}