AcWing 238. $\Large\color{blue}{【算法提高课】银河英雄传说（带权并查集）}$    原题链接    简单

作者： 作者的头像   incra ,  2022-11-27 08:00:22 ,  所有人可见 ,  阅读 2507

45


2

<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

有一个划分为 $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 \\le 30000 , T \\le 500000$

输入样例：

4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例：

-1
1

思路

这题也是带权并查集，如果还不懂的话，可以看看这篇题解里的图。
这里的权值在$find$之后表示的是当前点到根的战舰数量（包括自己和根）
注意：这里一定要第一棵树插到第二棵树上，因为第一棵树是要排到第二棵树下面的！
这里的权值其实直接从根插到另一个根上的权值就是第一棵树的节点数量（舰队数量）

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30010;
int n = 30000,m;
int p[N],d[N],s[N];
int find (int x) {
    if (p[x] != x) {
        int rx = find (p[x]);
        d[x] += d[p[x]];
        p[x] = rx;
    }
    return p[x];
}
int main () {
    cin >> m;
    for (int i = 1;i <= n;i++) p[i] = i,s[i] = 1;
    while (m--) {
        char op;
        int a,b;
        cin >> op >> a >> b;
        int ra = find (a),rb = find (b);
        if (op == 'M') {
            if (ra != rb) {
                p[ra] = rb;
                d[ra] = s[rb];
                s[rb] += s[ra];
            }
        }
        else {
            if (ra != rb) puts ("-1");
            else cout << max (0,abs (d[a] - d[b]) - 1) << endl;
        } 
    }
    return 0;
}

5 评论

用户头像
年为高远   2024-03-24 19:55         踩      回复

为什么d[x] += d[p[x]];这句话不能写在寻找父亲节点int rx = find (p[x]);的前面

用户头像
incra   2024-03-25 17:50         踩      回复

d[p[x]]此时应该表示p[x]到根的距离

用户头像
年为高远   2024-03-26 11:23    回复了 incra 的评论         踩      回复

懂了，谢谢

用户头像
化倾   2023-10-03 22:22         踩      回复

根节点到根节点的距离d[root]为0，这个特判一下就行，也就是说不需要存储根节点到根节点的距离d[root]，可以将d[root]这个值设为该连通块的大小，从而节省一个size数组

from typing import *
from math import *
from queue import PriorityQueue,Queue
import sys
# by hangpengjie

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

# slove question
# 对于rank数组，根节点保存节点个数，非根节点保存到根节点距离
class UF:
    def __init__(self,n:int) -> None:
        self.parent = [i for i in range(n + 1)]
        self.rank = [1] * (n + 1)
    def find(self,x:int) -> (int,int):
        if x == self.parent[x]:
            return (x, 0)
        par,dis = self.find(self.parent[x])
        self.rank[x] += dis
        self.parent[x] = par
        return (self.parent[x],self.rank[x])
    def merge(self,x:int,y:int) -> None:
        px,_ = self.find(x)
        py,_ = self.find(y)
        if px == py:
            return
        self.parent[px] = py
        self.rank[px],self.rank[py] = self.rank[py], self.rank[py] + self.rank[px]

def slove()->None:
    t = II()
    uf = UF(int(3e4+10))
    for _ in range(t):
        a = LI()
        if a[0] == 'M':
            uf.merge(int(a[1]),int(a[2]))
        else:
            px,dx = uf.find(int(a[1]))
            py,dy = uf.find(int(a[2]))
            if px == py:
                # 这里一定要跟0做比较取最大值，因为相邻节点为0，相同节点也为0，如果不做比较，相同节点会输出-1
                print(max(abs(dx-dy)-1,0))
            else:
                print(-1)




def __main__():
    T = 1
    while T:
        T -= 1
        slove()

if __name__ == '__main__':
    __main__()
用户头像
incra   2023-10-04 07:53         踩      回复

做并查集只有两个数组时，可以全部放在一个数组里做