Suppose you have a set of sets of integers. It's possible that some of the sets will overlap (i.e. sharing elements). You could get rid of the overlaps by deleting elements from the sets, but then some of them might end up empty; that would be a shame. Can we make all the sets disjoint without emptying any of them?
Note that in this situation, there's never any reason to leave multiple elements in a set, so this problem can always be solved by reducing each set to just one element. That's the version of the problem we're solving here.
The task
Write a program or function, as follows:
Input: A list of sets of integers.
Output: A list of integers, of the same length as the input, for which:
- All integers in the output are distinct; and
- Each integer in the output is an element of the corresponding set of the input.
Clarifications
- You can represent a set as a list if you wish (or whatever's appropriate for your language), disregarding the order of elements.
- You don't have to handle the case where no solution exists (i.e. there will always be at least one solution).
- There might be more than one solution. Your algorithm must always produce a valid solution, but is allowed to be nondeterministic (i.e. it's OK if it picks a different valid solution each time it runs).
- The number of distinct integers appearing in the input, n, will be equal to the number of sets in the input, and for simplicity, will be the integers from 1 to n inclusive (as their actual values don't matter). It's up to you whether you wish to exploit this fact or not.
Testcases
[{1,2},{1,3},{1,4},{3,4}] -> [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -> [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -> [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]
Victory condition
A program requires an optimal time complexity to win, i.e. if an algorithm with a better time complexity is found, it disqualifies all slower entries. (You can assume that your language's builtins run as fast as possible, e.g. you can assume that a sorting builtin runs in time O(n log n). Likewise, assume that all integers of comparable size to n can be added, multiplied, etc. in constant time.)
Because an optimal time complexity is likely fairly easy to obtain in most languages, the winner will therefore be the shortest program among those with the winning time complexity, measured in bytes.