UVa 1329 - Corporative Network Union Find题解

浏览数：20 / 时间：2015年06月09日

UVa的题目好多，本题是数据结构的运用，就是Union Find并查集的运用。主要使用路径压缩。甚至不需要合并树了，因为没有重复的连线和修改单亲节点的操作。

郁闷的就是不太熟悉这个Oj系统，居然使用库中的abs就会WA，自己写了个abs小函数就过了。

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4075

#include <stdio.h>

const int MAX_N = 20005;
const int MOD = 1000;
//在UVa使用库的abs居然WA，浪费好多时间
inline int abs(int a) { return a < 0? -a : a; }

struct Subset
{
	int p, w;
};

Subset subs[MAX_N];

int findParent(int x)
{
	if (subs[x].p != x)
	{
		int p = subs[x].p;
		subs[x].p = findParent(subs[x].p);
		subs[x].w = (subs[x].w + subs[p].w);
	}
	return subs[x].p;
}

void initSubs(int N)
{
	for (int i = 1; i <= N; i++)
	{
		subs[i].p = i;
		subs[i].w = 0;
	}
}

int main()
{
	int T, N, i, j;
	char cmd;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &N);
		getchar();
		initSubs(N);
		while ((cmd = getchar()) && cmd != 'O')
		{
			if (cmd == 'E')
			{
				scanf("%d", &i);
				subs[i].p = findParent(i);
				printf("%d\n", subs[i].w);
			}
			else
			{
				scanf("%d %d", &i, &j);
				subs[i].w = (abs(j - i))%MOD;
				subs[i].p = j;//不存在重复连线和更改parent，故此直接连就ok
			}
			getchar();
		}
	}
	return 0;
}

UVa 1329 - Corporative Network Union Find题解,古老的榕树,5-wow.com

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

UVa 1329 - Corporative Network Union Find题解