UVALive 3027 - Corporative Network（帶權并查集）

題目大意：

輸入t表示一共有 t 組測試資料，輸入 n 表示有n座城市，然後輸入一些指令，這些指令以字母‘O’ 結束，E i 表示 i 城市到他的父親節點的距離，I i j表示将 i 和 j 城連起來，j 是 i 的父親。

解題思路：

帶權并查集。比賽的時候也沒想到，實際上和之前并查集差不多，隻要改一下find函數就可以了，再維護一個dis數組，dis i 表示 i 城到父節點的距離是多少（距離abs（i-j）%1000），每一個E指令 輸出一個距離。

對find函數的解釋：x節點到x根節點的距離 = x的距離到x父親節點的距離+父親節點根節點的距離（套娃），遞歸的去求距離，最終更新的dis[x] 即為 x 到根節點的距離。

AC代碼：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace  std;
const int _max = 2e4+50;
int f[_max],dis[_max],t,n;
int find(int x)//路徑壓縮+尋根+求距離
{
	if(x==f[x])
	  return x;
	else
	{
		int t=f[x];//x的父親節點
		f[x]=find(f[x]);//父親節點去尋根
		dis[x]+=dis[t];//遞歸的去更新距離
		return f[x];
	}
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<=n;i++)
		{
		  f[i]=i;
		  dis[i]=0;
		}
		char ch;
		while(cin>>ch)
		{
			if(ch=='O')
			  break;
			int i,j;
			if(ch=='I')
			{
				cin>>i>>j;
				f[i]=j;
				dis[i]=abs(i-j)%1000;//更新後距離也要更新
			}
			else
			{
				cin>>i;
				find(i);//求i節點到根節點的距離
				cout<<dis[i]<<endl;
			}
		}
	}
	//system("pause");
	return 0;
}