A chaotic Ruby solution


  • 0
    A

    I'm not an algorithm guy so I don't know what is union find.

    My idea is to assign a representative to each circle. The representative can be anybody in that circle. Each time the traversal hit a person, find all the known circles he is in, and update those circles representative with the current person. In the end, I can work out the answer just by counting how many representatives.

    require 'set'
    
    def find_circle_num(m)
      circles = Array.new(m.size, nil)
      m.each_with_index do |ary, i|
        relations = i.times.with_object(Set.new) {|j, set| set << circles[j] if ary[j] == 1}
        circles[i] = i
        i.times {|j| circles[j] = i if relations.include?(circles[j])}
      end
      circles.tap(&:uniq!).size
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.