LA 3027 Corporative Network / 并查集

2种操作        I u v 把u的父节点设为v 距离为fabs(u-v)%1000        E u求u到根节点的距离

设dis[i] 为i节点到父节点的距离

在并查集压缩路径时更新dis数组

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 20010;
int dis[maxn], pa[maxn];

int find(int x)
{
	if(x != pa[x])
	{
		int root = find(pa[x]);
		dis[x] += dis[pa[x]];
		pa[x] = root;
		return pa[x];
	}
	else
		return x;
}
int main()
{
	int T, n;
	int u, v;
	scanf("%d", &T);
	while(T--)
	{
		char s[10];
		scanf("%d", &n);
		for(int i = 0; i <= n; i++)
		{
			pa[i] = i;
			dis[i] = 0;
		}
		while(scanf("%s", s) && s[0] != ‘O‘)
		{
			if(s[0] == ‘E‘)
			{
				scanf("%d", &u);
				find(u);
				printf("%d\n", dis[u]);
			}
			else
			{
				scanf("%d %d", &u, &v);
				dis[u] = abs(u-v) % 1000;
				pa[u] = v;
			}
		}
	}
	return 0;
}


 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。