HDU 3635 Dragon Balls 七龍珠 Union Find算法

HDU 3635 Dragon Balls 七龍珠 Union Find算法

孫悟空要尋找七龍珠，這回是七龍珠的增強版了，因為這些龍珠會衍生，最後不止七顆龍珠了。

悟空帶著布瑪的龍珠雷達探測器出發了，卻發現布瑪的龍珠雷達探測器的程序太垃圾了，所以找到我們這些ACM高手為龍珠雷達探測器寫個程序，要求可以顯示某顆龍珠所在的城市的位置，該龍珠所在的城市共有多少顆龍珠，龍珠移動過的次數。

布瑪是個有錢人啊，寫個程序我要價5百萬，不算過分吧。因為本程序需要用到Union Find（並查集）算法，而且最困難的部分是如何壓縮路徑，不壓縮路徑自然容易做到，要壓縮路徑可以使得程序加快很多，故此要價5百萬，O(∩_∩)O哈哈~。

路徑壓縮的思路是：

增加一個額外的移動記錄次數，方便查找父母節點的時候更新孩子節點。

壓縮路徑之後程序塊上100ms+；效果還是可以的。

不壓縮路徑的話，就直接接在一棵樹上，計算移動次數的時候，直接計算到父母節點的距離就可以了。

Union Find的靈活運用，優化好的話，達到5星級難度的題目。

#include 

const int MAX_N = 10001;
struct Subset
{
	int xp, yNumBall, zTrans, addTrans;
};

Subset subs[MAX_N];
int N;

void initSubs()
{
	for (int i = 1; i <= N; i++)
	{
		subs[i].xp = 0;
		subs[i].yNumBall = 1;
		subs[i].zTrans = 0;
		subs[i].addTrans = 0;//the main help for path compression
	}
}

int findParent(int x)//with path compression
{
	if (subs[x].xp)	//do not use 0 index.
	{
		int p = subs[x].xp;
		subs[x].xp = findParent(p);	//update parent
		
		subs[x].zTrans += subs[p].addTrans;//careful:Update transportation times
		subs[x].addTrans += subs[p].addTrans;	//Watch out: +=, not =
		return subs[x].xp;
	}
	return x;
}

int findParent_2(int x)//without path compression
{
	int p = x;
	if (subs[x].xp)	//do not use 0 index.
	{
		p = findParent(subs[x].xp);	//update parent
		subs[x].zTrans = subs[subs[x].xp].zTrans+1;//Update transportation times
	}
	return p;
}

void unionTwo(int x, int y)
{
	int xp = findParent(x);
	int yp = findParent(y);
	if (xp == yp) return ;

	subs[xp].xp = yp;	//It should be yp, not y. add to its parent directly
	subs[yp].yNumBall += subs[xp].yNumBall;	//only record balls in parent
	subs[xp].addTrans++;	//transportation happen, add one more trans
	subs[xp].zTrans++;	//Watch out: update self's trans
}

int main()
{
	int T, Q, a, b;	//N cities and balls, Q quests
	char cmd;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		scanf("%d %d", &N, &Q);
		initSubs();

		printf("Case %d:\n", t);
		while (Q--)
		{
			getchar();	// get rid of '\n'
			scanf("%c %d", &cmd, &a);
			if (cmd == 'T')
			{
				scanf("%d", &b);
				unionTwo(a, b);
			}
			else
			{
				int ap = findParent(a);
				printf("%d %d %d\n", ap, subs[ap].yNumBall, subs[a].zTrans);
			}//balls recorded in parent, trans times recorded in self node
		}
	}
	return 0;
}