Java 降低无向图的时间复杂度

当输入较大时，BFS算法将一遍又一遍地运行相同的图组件，始终派生相同的 node 计数.这真是太可惜了.一种解决方案是立即重复第二次BFS，然后使用您在第一阶段中找到的计数来标记访问的 node .每当要在已经具有该标记的 node 上调用BFS时，只需返回该标记并跳过BFS执行即可.

备选方案:不相交集

你可以创造disjoint-set data structure分，而不是graph分.该 struct 知道 node 所属的component，并且可以在填充 struct 时跟踪组件的大小.它并不精确地跟踪图的所有边，而是每个 node 只维护一个链接，只是为了跟踪组件成员资格.

有几种可选的算法可以合并两个组件.一种是"按大小联盟"，这在这里似乎是合适的，因为我们对大小感兴趣.

下面是一个DisjointSets类的可能实现:

import java.util.*;

class DisjointSets<T> {
    private class Node {
        Node parent;
        int size;
        T key;

        Node(T key) {
            this.key = key;
            this.size = 1;  // The node starts as its own component
            this.parent = this;
        }
    }

    Map<T, Node> nodes = new HashMap<>();

    private Node find(T key) {
        Node node = nodes.computeIfAbsent(key, Node::new);
        while (node.parent != node) {
            node = node.parent = node.parent.parent; // Path halving
        }
        return node;
    }

    public void union(T keyA, T keyB) {
        Node nodeA = find(keyA);
        Node nodeB = find(keyB);
        if (nodeA == nodeB) return; // Already in same set
        if (nodeA.size < nodeB.size) {
            nodeA.parent = nodeB;
            nodeB.size += nodeA.size;
        } else {
            nodeB.parent = nodeA;
            nodeA.size += nodeB.size;
        }
    }

    public int size(T key) {
        return find(key).size;
    }
}

然后，solve函数可以是:

    public static List<Integer> solve(int N, List<Integer> from, List<Integer> to, List<Integer> tasks) {
        int n = from.size();
        DisjointSets<Integer> set = new DisjointSets<>();
        for (int i = 0; i < n; i++) {
            set.union(from.get(i), to.get(i)); // populate disjoint sets
        }
        List<Integer> result = new ArrayList<>();
        for (int node : tasks) {
            result.add(set.size(node));
        }
        return result;
    }