K-th Largest Connected Components —— atcoder372

11/4更新，今天学了并查集，发现这道题其实就是构造了一个并查集，amazing啊！

问题描述

有一个无向图，它有 N 个顶点和 0 条边。顶点编号为 1 至 N。

有Q次询问，每次询问是以下两种操作中的一种：

• 类型一：给定格式为 1 u v 的输入。为节点 u 和 v 之间建立一条边。
• 类型二：给定格式为 2 v k 的输入。打印节点 v 可达的节点中第 k 大的节点的值。

总结反思

一开始错误理解了题目，以为只在节点 v 的邻居节点之间找，后来学习了一下其他人提交的正确答案才知道，原来是要在 v 节点所有可达的节点中间去查找第 k 大的节点值。

这就有两个难点：

• 在两个节点建立联系之后如何更新各自可达的节点？——难点在于，对于 u 节点来说，不仅要把 v 节点纳入可达节点，v 节点可达的所有节点也都要纳入进来，怎样去做这件事情？如果按照常规的方式，似乎不太好做。

• 怎么用较小的时间复杂度找到这第 k 大的节点？——我一开始想到的方式是用 List<List<Integer>> 来存邻接表，在每加入一条边时都重新对该节点的所有邻居节点重新排序，这个时间复杂度必然是不满足要求的。

解决第一个问题的方法是——用 parents 数组来存储每个节点所属的图的根节点信息。当然，图是没有根节点的，这里只是把每一个图中的第一个节点作为了根节点，同时把这个根节点的值作为 key 来找到这整个图的所有节点。同时配套的还有 findParents 方法和 union 方法前者用来递归查找当前节点的所在图的根节点，当 u 和 v 节点的根节点不一致时，这个时候就需要更新可达信息了，更新的方法就是union方法，那么把哪个图合并到另一个图中呢？答案是把节点数少的合并到节点数多的图中，这样插入操作会少一些，为了保存这个信息，就有了 sizes 数组。

解决第二个问题的方法是——用 TreeSet 来保存图的节点信息，插入时的维护代价小，同时查找的代价相比 List 和 HashMap 也不是特别高。

import java.util.*;

/**
 * 总结：
 *  -1. TreeSet 的好处是可以动态地在每次插入时根据节点值维护顺序，
 *      缺点是相比于 List 和 Map O(1) 的查询复杂度略有不如，但是这是值得的，
 *      因为 Map 完全不能得到这个信息，而 List 想要得到这个信息就得排序，
 *      如果是一次插入所有节点再排序一次也还好，但是如果像这道题一样，
 *      每次插入之后都要更新顺序（因为每次插入玩之后下一次操作都有可能是查询），
 *      代价就太大了
 *  -2. 要灵活选择数据结构来存储信息
 */
public class KthLargestConnectedComponents {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();

        // 1. 为什么要定义这两个数组？
        // sizes 数组的作用是要根据两个图的节点多少，将节点少的图合并进节点多的图
        // parents 数组我觉得更应该叫 roots ，实际上存的就是 root 节点的值
        // 2. 而为什么不存 parent 的值，只存 root 节点的值呢？
        // 是因为这道题其实不关心整个图是怎么连接起来的，只关心哪些节点是连起来的，以及这些节点的大小顺序，
        // 那么只要能通过 parents 数组找到根节点，再通过根节点，找到那整个图的次序信息即可
        int[] parents = new int[N + 1];
        int[] sizes = new int[N + 1];
        Arrays.fill(parents, -1);
        Arrays.fill(sizes, 1);

        // 1. 为什么这里要用 Map 而不用 List 来存邻接表？
        // 因为用 List 存邻接表，相当于是把节点值和List下标一一映射了，
        // 然而List的下标是从零开始的，而节点值是从1开始的，用map就没有这个问题，稍微方便一点
        // 2. 为什么要用 TreeSet 来存兄弟节点？
        // (1) 因为需要维护兄弟节点的大小顺序，而TreeSet每插入一个节点的时间复杂度是logn，
        // 如果用List来存，那么需要在添加每一个节点之后，重新对整个List排序，这个代价太大了
        // (2) 另外，这样合并两棵树的代价也要小一些，但是这不是主要原因
        Map<Integer, TreeSet<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            TreeSet<Integer> vertices = new TreeSet<>(Collections.reverseOrder());
            vertices.add(i);
            graph.put(i, vertices);
        }

        for (int i = 0; i < Q; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                int u = sc.nextInt();
                int v = sc.nextInt();

                int rootU = findRoot(parents, u);
                int rootV = findRoot(parents, v);

                // 这里的逻辑是，两个节点之间有一条边，不只是这两个节点自己的事，
                // 而是通过这两个节点，两个节点各自所在的图连接到了一起，互相变得可达了，也就在检索范围内了，
                // 所以要通过 union 操作更新 parents 信息
                if (rootU != rootV) {
                    if (sizes[rootU] < sizes[rootV]) {
                        int temp = rootU;
                        rootU = rootV;
                        rootV = temp;
                    }

                    // 这里为什么还要把 rootV 这棵树的信息删掉？
                    // 感觉其实可以不删，只是删掉更节约空间，
                    // 想了想，还是要删的，如果不删的话，那么每个节点都要保存所有节点的信息，这个空间占用就很大了
                    union(parents, sizes, rootU, rootV);
                    graph.get(rootU).addAll(graph.get(rootV));
                    graph.remove(rootV);
                }
            } else if (op == 2) {
                int node = sc.nextInt();
                int k = sc.nextInt();

                TreeSet<Integer> vertices = graph.get(findRoot(parents, node));
                if (k > vertices.size()) {
                    System.out.println(-1);
                } else {
                    Iterator<Integer> iterator = vertices.iterator();
                    int index = 1;
                    while (iterator.hasNext()) {
                        Integer next = iterator.next();
                        if (index == k) {
                            System.out.println(next);
                            break;
                        }
                        index++;
                    }
                }
            }
        }
    }

    // 将 rootV 下面的节点合并到 rootU 所在的图中
    private static void union(int[] parents, int[] sizes, int rootU, int rootV) {
        parents[rootV] = rootU;
        sizes[rootU] += sizes[rootV];
    }

    private static int findRoot(int[] parents, int node) {
        if (parents[node] == -1) {
            return node;
        }
        // 这里为什么要递归更新？
        // 因为有可能上层节点的 parents 信息在做合并操作的时候已经更新过了，
        // 底层节点还需要通过递归的方式更新
        return parents[node] = findRoot(parents, parents[node]);
    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int N = 4;
//        int Q = 10;
//        TreeSet<Integer> set = new TreeSet<>();
//
//        List<List<Integer>> graph = new ArrayList<>();
//        for (int i = 0; i < N; i++) {
//            List<Integer> neighbors = new ArrayList<>();
//            neighbors.add(i);
//            graph.add(neighbors);
//        }
//        int[][] query = {
//                {1, 1, 2},
//                {2, 1, 1},
//                {2, 1, 2},
//                {2, 1, 3},
//                {1, 1, 3},
//                {1, 2, 3},
//                {1, 3, 4},
//                {2, 1, 1},
//                {2, 1, 3},
//                {2, 1, 5}
//        };
//        for (int i = 0; i < Q; i++) {
//            int op = query[i][0];
//            if (op == 1) {
//                int node1 = query[i][1] - 1;
//                int node2 = query[i][2] - 1;
//                graph.get(node1).add(node2);
//                Collections.sort(graph.get(node1), (n1, n2) -> {
//                    return n2 - n1;
//                });
//                graph.get(node2).add(node1);
//                Collections.sort(graph.get(node2), (n1, n2) -> {
//                    return n2 - n1;
//                });
//            } else if (op == 2) {
//                int node = query[i][1] - 1;
//                int k = query[i][2];
//                if (k > graph.get(node).size()) {
//                    System.out.println(-1);
//                } else {
//                    List<Integer> neighbors = graph.get(node);
//                    int result = neighbors.get(k - 1) + 1;
//                    System.out.println("从节点" + node + "的邻居" + neighbors + "中获取第" + k + "个元素：" + result);
//                }
//            }
//        }
//        System.out.println(graph);
//    }
}