LA 3027 Corporative Network / 并查集
2种操作 I u v 把u的父节点设为v 距离为fabs(u-v)%1000 E u求u到根节点的距离
设dis[i] 为i节点到父节点的距离
在并查集压缩路径时更新dis数组
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> using namespace std; const int maxn = 20010; int dis[maxn], pa[maxn]; int find(int x) { if(x != pa[x]) { int root = find(pa[x]); dis[x] += dis[pa[x]]; pa[x] = root; return pa[x]; } else return x; } int main() { int T, n; int u, v; scanf("%d", &T); while(T--) { char s[10]; scanf("%d", &n); for(int i = 0; i <= n; i++) { pa[i] = i; dis[i] = 0; } while(scanf("%s", s) && s[0] != ‘O‘) { if(s[0] == ‘E‘) { scanf("%d", &u); find(u); printf("%d\n", dis[u]); } else { scanf("%d %d", &u, &v); dis[u] = abs(u-v) % 1000; pa[u] = v; } } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。