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

Question

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

第 1 组：(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，如果它们进一步有界，您也可以使用 vectors 而不是 unordered_maps。

#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);
}

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

Group pairs of elements based on connecting element in C++

c++

algorithm

sorting

data-structures

c++17

时间复杂度

C++17 中的示例代码：