根据公共元素组合成对的整数 [英] combine pairs of integers based on common element

问题描述

假设我有一对整数，例如（1,3），（5,6），（7,8），（3,9），那么我想根据它们之间的共同元素将这对整数组合成唯一的集合即我可以组合（1,3）和（3,9），因为它们之间是3，所以上述输入的最终输出应该像这样（1,3,9），（5,6），（7,8 ）
一种方法可能是遍历此数组，并基于公共元素将其组合并从数组中删除第二对，这我认为这很耗时。
在C / C ++中执行此操作的有效方法是什么？

suppose I have pair of integers for example (1,3), (5,6), (7,8), (3,9) then I want to combine this pairs into unique sets based on common element amongst them i.e. I can combine (1,3) and (3,9) because 3 is common between them, So final output for above input should be like this (1,3,9), (5,6), (7,8) One way could be to iterate through this array and based on common elements combine it and delete second pair from array which I suppose is time consuming. What is the efficient way to do this in C/C++ ?

推荐答案

一种执行此操作的有效方法是将其视为图连通性问题。创建一个节点为整数对的图，如果两个节点对应的对具有公共元素，则在两个节点之间添加无向边。现在，在此图中找到连接的组件，并构建由组件中的节点所对应的对的并集构成的集合。

One efficient way of doing this is to think of it as a graph connectivity problem. Create a graph where the nodes are the pairs of integers and add an undirected edge between two nodes if the pairs they correspond to have a common element. Now, find the connected components in this graph and construct the sets formed by the unions of the pairs that the nodes in a component correspond to.

查找连接的组件需要 O（E）时间，如果存在 n <，则可能为 O（n ^ 2） / code>对。可以使用类似 heap 的结构来合并它们，每次插入将花费 O（log n）。因此，运行时间为 O（E + n log n），最多为 O（n ^ 2）。复杂度可能要低得多，具体取决于对中有多少个元素有共同点。

Finding connected components takes O(E) time, which could be O(n^2) if there are n pairs. Merging them all can be done with a heap-like structure and that would take O(log n) per insertion. Thus the runtime is O(E + n log n) which is at most O(n^2). The complexity could be much lower depending on how many of the pairs have elements in common.

这篇关于根据公共元素组合成对的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！