洛谷P1196 银河英雄传说

大意:你有30000个队列,第i个队列中只有i

有T个操作,1,把某个队列头接到另一个队列尾。

2,问两个元素之间的距离。

本题主要有三种解法。

①带权并查集。

具体来说就是,并查集维护当前集合的大小,这个点距离代表元(队首)的边数。

然后把合并和路径压缩魔改一下。询问的时候就直接取距离之差。

 #include <cstdio>

 const int N = ;

 int fa[N], sum[N], siz[N];
char str[]; inline int find(int x, int &s) {
if(fa[x] == x) {
s = ;
return x;
}
int t = find(fa[x], s);
s += sum[x];
sum[x] = s;
return fa[x] = t;
} inline void merge(int x, int y) {
int a, b;
x = find(x, a);
y = find(y, b);
fa[x] = y;
sum[x] = siz[y];
siz[y] += siz[x];
return;
} inline int ask(int x, int y) {
int a, b;
x = find(x, a);
y = find(y, b);
if(x != y) {
return -;
}
return (a > b ? a - b : b - a) - ;
} int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= ; i++) {
fa[i] = i;
siz[i] = ;
}
for(int i = , x, y; i <= n; i++) {
scanf("%s%d%d", str, &x, &y);
if(str[] == 'M') {
merge(x, y);
}
else {
printf("%d\n", ask(x, y));
}
} return ;
}

AC代码

②平衡树

这个太暴力了......开30000颗平衡树即可。

③离线(kruskal重构树)

重构的时候把顺序搞一下,然后提出来DFS序,直接回答询问。

上一篇:vs debug 快捷键


下一篇:广度优先搜索(BFS)----------------(TjuOj1140_Dungeon Master)