美团 小美的朋友关系 Java

import java.util.*;
import java.io.*;

public class Main {
    // 并查集：父节点映射 + 秩映射（按秩合并用）
    public static HashMap<Integer, Integer> parent = new HashMap<>();
  
    // 查找（路径压缩 + 自动初始化节点）
    public static int find(int x) {
        // 节点不存在则初始化：父节点是自己，秩为1
        parent.putIfAbsent(x, x);
        // 路径压缩（迭代版，避免递归栈溢出）
        while (!parent.get(x).equals(x)) {
            parent.put(x, parent.get(parent.get(x))); // 父节点指向祖父节点
            x = parent.get(x);
        }
        return x;
    }

    // 合并（按秩合并 + 路径压缩）
    public static void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;

        // 按秩合并：将秩小的树合并到秩大的树
        parent.put(rootY, rootX);
    }

    // 生成统一的边key（避免{a,b}和{b,a}重复）
    static String getRelationKey(int a, int b) {
        return a < b ? a + "," + b : b + "," + a;
    }

    public static void main(String[] args) throws IOException {
        // 替换Scanner为BufferedReader，提升输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int n = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        int q = Integer.parseInt(parts[2]);

        // 存储原始边
        Set<String> edges = new HashSet<>();
        for (int i = 0; i < m; ++i) {
            parts = br.readLine().split(" ");
            int a = Integer.parseInt(parts[0]);
            int b = Integer.parseInt(parts[1]);
            edges.add(getRelationKey(a, b));
        }

        // 存储有效操作（过滤无效删除）
        ArrayList<int[]> ops = new ArrayList<>();
        for (int i = 0; i < q; ++i) {
            parts = br.readLine().split(" ");
            int op = Integer.parseInt(parts[0]);
            int a = Integer.parseInt(parts[1]);
            int b = Integer.parseInt(parts[2]);

            if (op == 1) {
                String key = getRelationKey(a, b);
                if (edges.contains(key)) {
                    edges.remove(key);
                    ops.add(new int[]{op, a, b});
                }
            } else {
                ops.add(new int[]{op, a, b});
            }
        }

        // 初始化：合并所有未被删除的边（最终状态）
        for (String key : edges) {
            String[] nodes = key.split(",");
            int a = Integer.parseInt(nodes[0]);
            int b = Integer.parseInt(nodes[1]);
            merge(a, b);
        }

        // 倒序处理操作，记录答案
        List<Boolean> answers = new ArrayList<>();
        for (int i = ops.size() - 1; i >= 0; i--) {
            int[] op = ops.get(i);
            if (op[0] == 1) {
                // 原删除操作 → 逆操作：合并
                merge(op[1], op[2]);
            } else {
                // 原查询操作：判断是否连通
                boolean connected = find(op[1]) == find(op[2]);
                answers.add(connected);
            }
        }

        // 逆序输出答案
        for (int i = answers.size() - 1; i >= 0; --i) {
            System.out.println(answers.get(i) ? "Yes" : "No");
        }
    }
}