Post History

One way of specifying what you want is that you want the equivalence classes of the equivalence relation generated by saying that pairs (a, b) and (x, y) are equal when either a = x or b = y. The famous [union-find algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) solves exactly the problem of incrementally computing representatives for an equivalence relation as more generating identifications are added.

In your case, you can simply maintain a hash map, e.g. a Python dictionary, (or an array if your IDs are dense) that maps `car_id` to a pair's ID in the union-find data structure, and similarly for `user_id`. You then simply iterate over all the pairs looking up the union-find ID in each of these maps and equating ("unioning") it with the union-find ID of the pair you're currently considering. If one or both of the maps don't have an entry for the current pair, insert the representative ID you got back from unioning with the other or the current pair's ID if entries were missing from both maps into the map(s) with the missing entry.

The hash table look-ups are effectively constant-time and union-find, famously, has an inverse Ackermann amortized time-complexity that might as well be constant-time. This gives an algorithm that's effectively linear-time in the number of pairs. The above algorithm will automatically handle duplicates, but you could also remove duplicates first. If you actually want to keep track of the duplicates (via some surrogate key effectively), you can easily just have the union-find ID be based on the surrogate key, e.g. the index in the list of pairs or you could just go back over the list after the fact grouping pairs by the representative IDs.

Union-find is a fairly easy algorithm to implement, though I recommend a slight variation, also easy to implement, called Rem's algorithm. See [Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure](https://www.ii.uib.no/~fredrikm/fredrik/papers/SEA2010.pdf).

I'm pretty sure there are other, quite possibly better, ways of doing this, but this is already relatively simple and efficient.