c++里有一堆 pair, 比如<1,2>, <3,2>, <3,6>, <6,3>, <6,4>, <5,8>, <9,8>, <10,12>, <12,11>, 把 pair 里不管第一个还是第二个元素相同的 pair 划分为一组, 最后的结果是[<1,2>, <3,2>, <3,6>,<6,3>, <6,4>], [<5,8>, <9,8>], [<10,12>, <12,11>]，我自己是用循环实现的，但是 pair 多的时候效率太差， 请问一下各位有什么好的算法可以实现吗？谢谢！
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2205 days ago, the information mentioned may be changed or developed.
 |
1
siyemiaokube May 10, 2020 via iPhone
谢不邀，不确定你说的啥
方法一：建图，二元组就是一条边。缺点是不适合动态维护 方法二：hash+并查集。适合动态维护，效率略低。 |
 |
2
luckyrayyy May 10, 2020
把所有 pair 用图来表示，然后判断里面一共有几组连通图？ dfs 搜？
|
|
3
siyemiaokube May 10, 2020 via iPhone
update：不需要建图，直接把一个 pair<a,b>当成并查集里的 merge （ a，b ）就行了
|
 |
4
xupefei May 10, 2020
一楼说的对。
把 pair 中的每个元素作为 key 建立哈希表，然后用 union-find 。时间复杂度 O(\log n)。 |
 |
5
ksedz May 10, 2020
至少要循环遍历一次的
如果你是指多次操作慢可以考虑加结果缓存或在产生时打标记 |
 |
6
Allianzcortex May 10, 2020
1 楼 + 1，Hash + 并查集，楼主的需求和这道题很相似： https://leetcode-cn.com/problems/baby-names-lcci/
|
 |
7
QingchuanZhang May 11, 2020
|
 |
8
lithbitren May 11, 2020
楼里的这两道并查集题的最短 py 解法都是俺写的，时间上一道 100%一道 98%，理论上 c++也可以按照相同原理实现。
|
 |
9
ihourui OP @siyemiaokube 谢谢，我试一下你的做法，非常感谢！
|
|
10
ihourui OP @luckyrayyy 我就是用 dfs 递归搞的，但是 pair 多的时候时间消耗很大。
|
 |
11
sarvatathagata May 11, 2020
如果没有修改的话，可以做到线性。先与一楼的做法一样 hash，然后对于出现过的每一个 first 元素和每一个 second 元素建虚点，<a,b>和第一类虚点{a}还有第二类虚点{b}连边。然后跑 dfs 就可以线性了。
|
Select Language