基于 C++ 中的连接元素对元素进行分组

Question

假设我有一对整数，例如： [(1,2), (3,4), (2,3), (3,5), (7, 8), (7,9)] 我想根据它们之间的连接元素将这些对排序到唯一的组中，即如果元素与同一组中的另一对共享公共元素，那么它们应该放入同一组中。因此，在上面的示例中，我们最终将得到两个组：

Group1：(1,2), (2,3), ( 3,4), (3,5)

第 2 组：(7,8), (7, 9 ）

关键是应该至少有一个引用出现在前一对中（即这个是连接对的定义），并且前一对可以是之前对中的任何一对，而不是直接在其之前的对。如果没有“连接对”，那么该对应该单独分离到一个新组

我知道这可以通过图形来完成，但是有人能够建议最有效且易于在 C++ 中实现的解决方案吗？

谢谢！

Answer 1

假设：成对有序。 (a,a),(a,b),(b,a) 是有效输入。

是的，这个问题可以使用无向图来解决。

对于每个给定的对 (a, b)，在 a 和 b 之间创建一条无向边。现在遍历该图以找到其连接的组件。记住每个节点的组件，例如。通过给它们着色。最后，对于所有输入对，检查它们所属的组件（也称为颜色）并将其添加到该组中。单独对每个组进行排序并输出。

时间复杂度

令n 为输入中的对数。

遍历：O(n)。我们构建的图中有 O(n) 个节点和 O(n) 个边。对于下面给定的 C++ 代码 - 我们将最多访问每条边两次（由于无向图）。任何已访问的节点都会从第一行本身返回，这发生在该节点上的每个事件边上。所有节点上此类关联边的计数为 O(n)。

排序：O(n * log n)，因为组的最大大小可以是O(n)

总计： O(n * log n)

C++17 中的示例代码：

我将图存储为邻接列表 adj 并使用深度优先遍历 dfs.假设输入整数适合 int，如果它们有进一步的限制，您还可以使用 vector 代替 unordered_map。

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm> 

using namespace std;
       
unordered_set<int> vis;
unordered_map<int, vector<int>> adj;

void dfs(int u, vector<int>& cur_group) {
    if (vis.count(u)) return;
    vis.insert(u);
    cur_group.push_back(u);
    for (auto v: adj[u]) {
        dfs(v, cur_group);
    }
};

int main() {
    vector<pair<int, int>> input = {{4,3},{1,9},{7,9},{2,4},{3,2},{9,7},{9,9}};

    // create undirected graph
    for (auto [u, v]: input) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int component_count = 0;
    unordered_map<int, int> color;
    // traverse all nodes and color all nodes reachable.
    for (auto [u, v]: input) {
        // If u is traversed v must be traversed as they are adjacent
        if (vis.count(u) == 0) {
            vector<int> cur_group;
            dfs(u, cur_group);
            for (int v: cur_group) {
                color[v] = component_count;
            }
            component_count++;
        }
    }

    // push input pairs into their corresponding color component
    vector<vector<pair<int, int>>> components(component_count);
    for (auto p: input) {
        components[color[p.first]].push_back(p);
    }

    // sort and output each color component separately
    for (auto& component: components) {
        sort(component.begin(), component.end());
        for (auto [u, v]: component) {
            cout << '(' << u << ',' << v << "),";
        }
        cout << endl;
    }

    return 0;
}

输出：

(2,4),(3,2),(4,3),
(1,9),(7,9),(9,7),(9,9),

Answer 2

O(n^2) 解决方案，这将为您提供组数，可以修改代码以获取组值

public static void main(String[] args) {

    int[][] input = {{1, 2}, {3, 4}, {2, 3}, {3, 5}, {7, 8}, {7, 9}};

    int count = 0;

    Set<Integer> seen = new HashSet<>();

    for (int i = 0; i < input.length; i++) {

        if (seen.contains(i)) {
            continue;
        }

        Set<Integer> aGroup = new HashSet<>();
        aGroup.add(input[i][0]);
        aGroup.add(input[i][1]);

        count++;
        seen.add(i);

        for (int j = i + 1; j < input.length; ) {

            if (!seen.contains(j) && (aGroup.contains(input[j][0]) || aGroup.contains(input[j][1]))) {
                seen.add(j);
                aGroup.add(input[j][0]);
                aGroup.add(input[j][1]);

                j = i + 1;
            } else {
                j++;
            }
        }
    }

    System.out.println(count);
}