Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Add Comment
Please, Sign In to add comment