基于连接的顶点对构建图

Question

我需要检查将创建多少个单独的图，其中“n 行包含正整数对，其中每对标识图中两个顶点之间的连接。”。 假设我们有 3 对：[4 3]、[1 4]、[5 6]。 答案是 2，因为 [4 3]&[1 4] 将合并成一个图：[1 3 4]，第二个是 [5 6]。 如果我们再添加一对：[4 3]、[1 4]、[5 6]、[4 6]，答案将为 1（只有 1 个图：[1 3 4 5 6] 连接）。

我设法用Java解决了这个问题，但是效率不高，对于超过10000对以上的情况，速度非常慢。代码看起来或多或少是这样的：

    Set<Pair> connectionsSet;
    HashSet<TreeSet<Integer>> createdConnections;
    
    public void createGraphs() {
        for (Pair pair : connectionsSet) {
            boolean foundLeft = false, foundRight = false;
            for (TreeSet<Integer> singleSet : createdConnections) {
                if (singleSet.contains(pair.getLeft())) foundLeft = true;
                if (singleSet.contains(pair.getRight())) foundRight = true;
            }
            if (!foundLeft && !foundRight)
                addNewGraph(pair);
            else if (foundLeft && !foundRight)
                addToExistingGraph(pair, Constants.LEFT);
            else if (!foundLeft && foundRight)
                addToExistingGraph(pair, Constants.RIGHT);
            else if (foundLeft && foundRight)
                mergeGraphs(pair);
        }
    }

    private void addNewGraph(Pair pair) {
        createdConnections.add(new TreeSet<>(pair.asList()));
    }

    private void addToExistingGraph(Pair pair, String side) {
        for (TreeSet<Integer> singleSet : createdConnections) {
            if (side.equals(Constants.LEFT) && singleSet.contains(pair.getLeft()))
                singleSet.add(pair.getRight());
            if (side.equals(Constants.RIGHT) && singleSet.contains(pair.getRight()))
                singleSet.add(pair.getLeft());
        }
    }

    private void mergeGraphs(Pair pair) {
        Optional<TreeSet<Integer>> leftSetOptional = getOptional(pair.getLeft());
        Optional<TreeSet<Integer>> rightSetOptional = getOptional(pair.getRight());

        if (leftSetOptional.isPresent() && rightSetOptional.isPresent()){
            TreeSet<Integer> leftSet = leftSetOptional.get();
            TreeSet<Integer> rightSet = rightSetOptional.get();

            rightSet.addAll(leftSet);

            createdConnections.removeIf(singleSet -> singleSet.contains(pair.getLeft()));
            createdConnections.removeIf(singleSet -> singleSet.contains(pair.getRight()));
            createdConnections.add(rightSet);

        }
    }

如何提高性能？我并不是要求一个现成的解决方案，但也许有一种我不知道的算法可以显着加快速度？

Answer 1

要获取连接组件的数量，您可以使用不相交集。这是一个简单的实现，假设输入是

List

边。

Map<Integer, Integer> parent = new HashMap<>();
int find(int x) {
    int p = parent.getOrDefault(x, x);
    if (p != x) p = find(p);
    parent.put(x, p);
    return p;
}
public int numConnectedComponents(List<Pair> edges) {
    for (var e : edges) {
        int lPar = find(e.getLeft()), rPar = find(e.getRight());
        parent.put(lPar, rPar);
    }
    int comps = 0;
    for (var e : parent.entrySet())
        if (find(e.getKey()) == e.getValue()) ++comps;
    return comps;
}