基于顶点对构建图：如何提升大规模连通分量计算性能？

问题背景 #

给定n组正整数对，每组数对代表图中两个顶点的连接，需计算最终形成的独立连通分量的数量。示例：

• 3组数对[4 3]、[1 4]、[5 6]，结果为2，对应连通分量[1,3,4]和[5,6]；
• 新增数对[4 6]后，结果为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);

    }
}

核心疑问 #

我并非需要现成解决方案，而是想了解是否有可显著提升性能的算法？

内容的提问来源于stack exchange，提问作者Mio