You are viewing a single comment's thread. Return to all comments →
def DFS(graph, current_vertex, visited, country) visited[current_vertex] = country for vertex in graph[current_vertex] do DFS(graph, vertex, visited, country) if visited[vertex] == -1 end end def journeyToMoon(n, astronaut) graph = Array.new(n) { Array.new } astronaut.each { |i,j| graph[i] << j; graph[j] << i } visited = Array.new(n,-1) n.times { |i| DFS(graph,i,visited,i) if visited[i] == -1 } countries_size = Array.new(visited.length,0) visited.each { |i| countries_size[i] += 1 } countries_size.delete(0) countries_keys = countries_size.tally.keys countries_values = countries_size.tally.values counter = 0 countries_keys.each_index { |i| counter += countries_keys[i]**2 * countries_values[i]*(countries_values[i]-1)/2 } country_combinations = countries_keys.each_index.to_a.combination(2).to_a country_combinations.each { |pair| counter += countries_keys[pair[0]]*countries_keys[pair[1]]*countries_values[pair[0]]*countries_values[pair[1]] } counter end
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
Ruby