1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

class DistinctSets

    class Node
        attr_reader :name, :merged

        def initialize(name)
            @name = name
            @neighbours = {}
            @merged = false
        end

        def meet_and_greet(nodes)
            for node in nodes
                name = node.name
                @neighbours[name] = node unless @name == name
            end
        end

        def merge_names(names)
            @merged = true
            mynames = @neighbours.keys
            union = names << @name | mynames
            for n in (mynames - names)
                node  = @neighbours[n]
                union = node.merge_names(union) unless node.merged
            end
            union
        end
    end

    def initialize(sets)
        @sets = sets
        @distinct = nil
    end

    def distinct
        if @distinct.nil?
            graph = {}
            @distinct = []
            for s in @sets
                if s.empty?
                    # Compatibility with posted test cases
                    @distinct |= [[]]
                else
                    sn = s.map {|n| graph[n] ||= Node.new(n)}
                    for s1 in sn
                        s1.meet_and_greet(sn)
                    end
                end
            end
            nodes = graph.values
            while (node = nodes.pop)
                next if node.merged
                set = node.merge_names([])
                @distinct << set.sort do |a, b|
                    if a.kind_of?(Numeric) and b.kind_of?(Numeric)
                        a <=> b
                    else
                        a.to_s <=> b.to_s
                    end
                end
            end
        end
        return @distinct
    end

end


def distinct_sets(sets)
    DistinctSets.new(sets).distinct
end