import collections


def transpose_dict_with_sets(dict_in):
    """
    Given a mapping X: key -> set of values, produce a mapping Y of the same type, where
        for every combination of a, b for which a in X[b], the following holds: b in Y[a].
    """
    result = collections.defaultdict(set)
    for key, values in dict_in.items():
        for val in values:
            result[val].add(key)
    return result