UVAILIVE-3027:Corporative Network

Corporative Network
ソース:UVAILIVE
ラベル:データ構造、検索集
参考資料:
似たようなテーマ:
テーマ
A very big coporation is developing its coporative network.In the begining each of the N enterpriss of the coporation,numerated from 1 to N,organized its coputing and telecomication center.Soon,formation ofeach of them served by a single coputting and telecommunication center as follow.The coporation chorse one of the exining center I(serving the cluster A)and one of the nterpress J in Some other cluster B(not necenter)and link them with telecomication line.The length of the line between the enterprinses I and J is＿I−J(mod1000).In such a way the two old clters areined in new cluster,served by the centr of the old cluster B.Unfortututunaly affteraaaaaaaaftereeinthe sum of the lengths of the linininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininto answerthe questions of the users.Your program has to be ready to solive more than one test case.
入力
The first line of the input file will contains the number T of the test cases.Each test will start with the number N of enterprinses(5≦N≦20000).The n some number of lines(no more the moners the the the will the condersons)will the montinners moners moners moners moners the moners moners moners moners monersI J-informing that the serving center I is linked to the enterprise J.The test case finishes with a line containing the word‘O’.The‘I’command are less than N.
出力
The output shound contain as many lineas as the number of'E'command in all test cases with a single number each-the asked sum of length of lineas connecting the corecting ponding enterpris with serving center.
入力サンプル
1 4 E 3 I 3 1 E 3 I 1 2 E 3 I 2 E 3 E 3 O
出力サンプル
0 2 3 5
問題を解く構想
そして思想を集める
参照コード

#include
#include
#define MAXN 20005
int pa[MAXN];
int dis[MAXN];//dis[u]：u        

int findset(int x){
	if(pa[x]!=x){
		int root=findset(pa[x]);
		dis[x]+=dis[pa[x]];
		return pa[x]=root;
	}
	return x;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,v,u;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			pa[i]=i;
			dis[i]=0;
		}
		
		char cmd[5];
		while(scanf("%s",cmd) && cmd[0]!='O'){
			if(cmd[0]=='E'){
				scanf("%d",&u);
				findset(u);
				printf("%d
",dis[u]);
			}
			else if(cmd[0]=='I'){
				scanf("%d%d",&u,&v);
				pa[u]=v;
				dis[u]=abs(u-v)%1000;
			} 
		}
	}
	return 0;
}