算法分析

并查集可以用于维护具有传递性关系的作用，每个集合的大小，绑定到根结点上，每个点到根结点的距离，绑定到每个元素的结点上

• 1、size[x]表示集合的大小，d[x]表示x到p[x]的距离

• 2、将第a列的船接在第b列的末尾，如图所示，相当于让每个点到pb的距离都加上size[pb]，由于存储并查集中存在路径压缩的效果，因此只需要将pa到pb的距离加上size[pb]即可，即d[pa] = size[pb]，其他跟着pa后面的元素会通过图片2操作对路径进行压缩且更新d[i]的值

• 3、路径压缩的过程

  • 1、找到根结点root

  • 2、计算父节点到上一个父节点的距离d[p[x]],同时进行路径压缩(路径压缩后，上一父节点即root)

  • 3、d[x]初始值是x到p[x]的距离，更新d[x]值，即d[x] = d[x] + d[p[x]]

注意：题目C操作问的是间隔多少条船，若a != b，则间隔abs(d[a] - d[b]) - 1条船，若a == b，则间隔0条船

时间复杂度

并查集操作接近$O(1)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
    static int N = 30010; 
    static int n,k;
    static int[] p = new int[N];
    static int[] size = new int[N];//集合的大小
    static int[] d = new int[N];//到根结点的距离
    static int find(int x)
    {
        if(p[x] != x)
        {
            int root = find(p[x]);
            d[x] += d[p[x]];
            p[x] = root;
        }
        return p[x];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        for(int i = 1;i <= 30000;i ++) 
        {
            p[i] = i;
            size[i] = 1;
        }
        for(int i = 0;i < n;i ++)
        {
            String[] s1 = br.readLine().split(" ");
            String op = s1[0];
            int a = Integer.parseInt(s1[1]);
            int b = Integer.parseInt(s1[2]);

            if(op.equals("M"))
            {
                int pa = find(a);
                int pb = find(b);
                p[pa] = pb;
                d[pa] = size[pb];
                size[pb] += size[pa];
            }
            else
            {
                int pa = find(a);
                int pb = find(b);
                if(pa != pb) log.write(-1 + "\n");
                else log.write(Math.max(0, Math.abs(d[a] - d[b]) - 1) + "\n");
            }
        }
        log.flush();
    }
}