这是一个创建于 1659 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 多的时候效率太差， 请问一下各位有什么好的算法可以实现吗？谢谢！
 |
1
siyemiaokube 2020-05-10 22:46:57 +08:00 via iPhone
谢不邀，不确定你说的啥
方法一：建图，二元组就是一条边。缺点是不适合动态维护 方法二：hash+并查集。适合动态维护，效率略低。 |
 |
2
luckyrayyy 2020-05-10 22:48:25 +08:00
把所有 pair 用图来表示，然后判断里面一共有几组连通图？ dfs 搜？
|
|
3
siyemiaokube 2020-05-10 22:51:22 +08:00 via iPhone
update：不需要建图，直接把一个 pair<a,b>当成并查集里的 merge （ a，b ）就行了
|
 |
4
xupefei 2020-05-10 22:59:10 +08:00
一楼说的对。
把 pair 中的每个元素作为 key 建立哈希表，然后用 union-find 。时间复杂度 O(\log n)。 |
 |
5
ksedz 2020-05-10 23:06:23 +08:00
至少要循环遍历一次的
如果你是指多次操作慢可以考虑加结果缓存或在产生时打标记 |
 |
6
Allianzcortex 2020-05-10 23:22:48 +08:00
1 楼 + 1，Hash + 并查集，楼主的需求和这道题很相似： https://leetcode-cn.com/problems/baby-names-lcci/
|
 |
7
QingchuanZhang 2020-05-11 01:12:52 +08:00
|
 |
8
lithbitren 2020-05-11 05:31:27 +08:00
楼里的这两道并查集题的最短 py 解法都是俺写的，时间上一道 100%一道 98%，理论上 c++也可以按照相同原理实现。
|
 |
9
ihourui OP @siyemiaokube 谢谢，我试一下你的做法，非常感谢！
|
|
10
ihourui OP @luckyrayyy 我就是用 dfs 递归搞的，但是 pair 多的时候时间消耗很大。
|
 |
11
sarvatathagata 2020-05-11 09:18:38 +08:00
如果没有修改的话，可以做到线性。先与一楼的做法一样 hash，然后对于出现过的每一个 first 元素和每一个 second 元素建虚点，<a,b>和第一类虚点{a}还有第二类虚点{b}连边。然后跑 dfs 就可以线性了。
|
Select Language