• 238. 银河英雄传说,带权值的并查集


    238. 银河英雄传说 - AcWing题库

    有一个划分为 N 列的星际战场,各列依次编号为 1,2,…,N。

    有 N 艘战舰,也依次编号为 1,2,…,N,其中第 i 号战舰处于第 i 列。

    有 T 条指令,每条指令格式为以下两种之一:

    1. M i j,表示让第 i 号战舰所在列的全部战舰保持原有顺序,接在第 j 号战舰所在列的尾部。
    2. C i j,表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。

    现在需要你编写一个程序,处理一系列的指令。

    输入格式

    第一行包含整数 T,表示共有 T 条指令。

    接下来 T 行,每行一个指令,指令有两种形式:M i j 或 C i j

    其中 M 和 C为大写字母表示指令类型,i 和 j 为整数,表示指令涉及的战舰编号。

    输出格式

    你的程序应当依次对输入的每一条指令进行分析和处理:

    如果是 M i j 形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

    如果是 C i j 形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第 i 号战舰与第 j 号战舰之间布置的战舰数目,如果第 i 号战舰与第 j 号战舰当前不在同一列上,则输出 −1。

    数据范围

    N≤30000,T≤500000

    输入样例:
    1. 4
    2. M 2 3
    3. C 1 2
    4. M 2 4
    5. C 4 2
    输出样例:
    1. -1
    2. 1

     解析:


    带权值的并查集
    p表示父节点,d表示当前节点到所在联通块的根节点的距离,s表示当前联通块的大小

     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. using namespace std;
    16. typedef long long LL;
    17. const int N = 3e4 + 5;
    18. int n;
    19. int p[N], s[N], d[N];
    20. int find(int a) {
    21. if (p[a]!=a) {
    22. int root = find(p[a]);
    23. d[a] += d[p[a]];
    24. p[a] = root;
    25. }
    26. return p[a];
    27. }
    28. int main() {
    29. scanf("%d", &n);
    30. for (int i = 1; i <= 3e4; i++) {
    31. p[i] = i;
    32. s[i] = 1;
    33. }
    34. char op[2];
    35. int a, b;
    36. while (n--) {
    37. scanf("%s%d%d", op, &a, &b);
    38. if (op[0] == 'M') {
    39. int pa = find(a), pb = find(b);
    40. if (pa != pb) {
    41. d[pa] = s[pb];
    42. s[pb] += s[pa];
    43. p[pa] = pb;
    44. }
    45. }
    46. else {
    47. int pa = find(a), pb = find(b);
    48. if (pa !=pb)cout << "-1" << endl;
    49. else {
    50. printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
    51. }
    52. }
    53. }
    54. return 0;
    55. }

  • 相关阅读:
    Linux 环境搭建以及xshell远程连接
    linux c与c++库互相调用
    关于通用相机库
    【Pytorch笔记】5.DataLoader、Dataset、自定义Dataset
    常见的损失函数
    IntelliJ IDEA 记学习笔 Maven自动导包 Auto Import
    【C++风云录】解锁智慧之门:物联网安全工具和库助力打造安全可靠的智能家居
    传统广电媒体为何选择上云?有何优势?
    爬虫都可以干什么?
    数据库优化【面试】
  • 原文地址:https://blog.csdn.net/Landing_on_Mars/article/details/133827371