AtCoder Beginner Contest 279 F BOX 并查集 （大意失荆州

前言

赛时一直RE，思路很清晰，不知道RE哪里。。qwq
赛后开断点发现，map的大小不变，
最后发现是一个if条件写错了，寄。

不知道为什么会想起 银河英雄传说

题意：

初始n个盒子，盒子$i$放着编号为$i$的小球
进行q次操作

• op1：将y盒子的小球移到x盒子中
• op2：将第k个球，加入到x盒子中
• op3：询问球x在哪个盒子中

思路：

我们看到op1，联想到集合的合并，于时想到并查集的操作
图中绿色的点代表盒子。

1. 经过 多个op1，op1，op1…我们可以用并查集把这些球合并到盒子2
2. 此时，突然有个 $o{p}_{1}12$, 那么我们$merge(box[1],box[2])$

merge(int x, int y){
	int fx = find(x), fy = find(y);
	p[fy] = fx;//根据题意合并
}
1
2
3
4

3. 误区：此时突然来个$o{p}_{2}2$，

假如新球，连到原来的盒子p[k] = find(box[2]) ,最后会使得新球在盒子1，其实新球在盒子2

因为p[box[2]] == p[box[1]]

做法：

• 对于每个盒子和点都编号
• 每次操作1后，把$y$盒子删除，新建一个$y‘$

box[y] = ++newBox;
1

What’s more

看了SSRS，好像可以用启发式合并，一开始我也是想用，但后面发现新开点，就可以解决了。

Java

package com.hgs.atcoder.abc.contest279.f;

/**
 * @author youtsuha
 * @version 1.0
 * Create by 2022/11/26 19:43
 */
import java.util.*;
import java.io.*;
public class Main{
    static FastScanner cin;
    static PrintWriter cout;

    private static void init()throws IOException {
        cin = new FastScanner(System.in);
        cout = new PrintWriter(System.out);
    }

    private static void close(){
        cout.close();
    }
    static int[] p;
    static int find(int x){
        if(x == p[x]) {
            return p[x];
        }
        return p[x] = find(p[x]);
    }
    private static void sol()throws IOException {
        int n = cin.nextInt(), m = cin.nextInt();
        int tot = n  + m;
        p = new int[tot*2 + 1];
        Map<Integer,Integer> curBox = new HashMap<>();
        Map<Integer,Integer> boxPre = new HashMap<>();
        int newBox = tot;
        //[1,tot] balls
        //[tot+1,tot*2] boxs
        for(int i = 1; i <= tot*2; i ++ ) {
            p[i] = i;
            if(i > tot && i <= tot + n){
                newBox++;
                curBox.put(i - tot,i);
                boxPre.put(i,i-tot);
            }else if(i <= n){
                p[i] = i + tot;
            }
        }
        int k = n;
        for(int i = 1; i <= m; i ++ ) {
            int op = cin.nextInt(), x = cin.nextInt();
            if(op == 1){
                int y = cin.nextInt();
                //y-->x
                int preY = curBox.get(y);
                p[preY] = p[curBox.get(x)];

                boxPre.put(++newBox,y);
                curBox.put(y,newBox);
            }else if(op == 2){
                k++;
                p[k] = curBox.get(x);
            }else {
                cout.println(boxPre.get(find(p[x])));
            }
        }

    }
    public static void main(String[] args) throws IOException {
        init();
        sol();
        close();
    }
}
class FastScanner {
    BufferedReader br;
    StringTokenizer st = new StringTokenizer("");

    public FastScanner(InputStream s) {
        br = new BufferedReader(new InputStreamReader(s));
    }

    public FastScanner(String s) throws FileNotFoundException {
        br = new BufferedReader(new FileReader(new File(s)));
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) { e.printStackTrace(); }
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106