POJ1962:Corporative Network(并查集)
Description
Input
E I – asking the length of the path from the enterprise I to its serving center in the moment;
I I 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 commands are less than N.
Output
Sample Input
1 4 E 3 I 3 1 E 3 I 1 2 E 3 I 2 4 E 3 O
Sample Output
0 2 3 5
Source
#include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <algorithm> using namespace std; #define ls 2*i #define rs 2*i+1 #define up(i,x,y) for(i=x;i<=y;i++) #define down(i,x,y) for(i=x;i>=y;i--) #define mem(a,x) memset(a,x,sizeof(a)) #define w(a) while(a) #define LL long long const double pi = acos(-1.0); #define Len 20005 #define mod 19999997 const int INF = 0x3f3f3f3f; int t,n; char str[5]; int father[Len],dis[Len]; int find(int x) { if(x == father[x]) return x; int fx = find(father[x]); dis[x] = dis[x]+dis[father[x]]; return father[x]=fx; } void solve(int x,int y) { int fx = find(x),fy = find(y); if(fx == fy) return; father[x] = x; dis[fx] = dis[x]; father[x] = y; dis[x] = abs(x-y)%1000; } int main() { int i,j,k,x,y; scanf("%d",&t); w(t--) { scanf("%d",&n); up(i,0,n) { father[i] = i; dis[i] = 0; } w(~scanf("%s",str)) { if(str[0]=='O') break; if(str[0]=='E') { scanf("%d",&x); find(x); printf("%d\n",dis[x]); } else { scanf("%d%d",&x,&y); solve(x,y); } } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。