Ruby Connected Components in a Graph
It Your solution being slow is not too much a matter of language here.
I will try highlighting ruby related things you could improve to make it more readable on one hand,
and algorithmic flaws on the other hand.

Ruby

Here I will point out some of the ruby code that could be improved. Note that this will not help
your solution to be much faster since it is mostly an algorithmic problem you have here.

Find Set

Your find_set method seems fine. It is a O(n) method. You have to go through every set to find
the one which includes the node you want. The #include? method of a set is constant in time, and
that is a good use of set here.

Make Set

Your make_set method could be made shorter and cleaner. For instance:

def make_set(n)
  Set.new((1..n).map { |i| Set.new([i]) })
end


Map + Inject

I would not recommand using #map and then #inject as it will create an intermediate array, and
because you can have all in the #inject, like:

vertices.inject(0) { |sum, set| set.size + 1 + sum }


And by the way, you can get rid of to_a since sets accept the #inject and #map methods too.

Method name

You should use snake case: roadsAndLibraries becomes roads_and_libraries.

Algorithmic enhancements

Unneeded computation

Itseems to me you don't need any computation if the road is more expensive than the library.
You can move this to the top of your roadsAndLibraries method.

return n * c_lib if c_road &gt; c_lib


Sets lookup

The main issue with your solution here is probably the lookup you do for each edge. You parse the
whole set of vertices for each city. This is expensive. You could try having a constant lookup
here that would help getting the connected component of a vertice on O(1).

You can use 2 arrays here. One for storing the connected components, like you already do. But
instead of storing them in a set, you can store them in an array, so they have an associated index.
Let's call it components.

And then the second array can be the lookup, we will call it component_index. For each node, you
store the index of its connected component. That way, all find_set has to do is to take the
stored index: components[component_index[a]] for city a.

Your main loop could look like:

cities.each do |a, b|
  first_set = component_index[a]
  second_set = component_index[b]
  next if first_set == second_set
  merge_components(component_index, components, first_set, second_set)
end


Merging components

Where the algorithm will spend time is when we merge components together. Here you will have to
update component indexes. What you have to see here is that it will be performed much less often
than the lookup, especially in case of strongly connected components, where first_set and
second_set of the main loop will be equal.

To merge 2 components, I would put the nodes of the smallest component into the largest one, to
avoid updating too many indexes. And then I would update the indexed component so that it contains
all nodes.

def merge_components(component_index, components, first_set, second_set)
  to = first_set
  from = second_set
  to, from = from, to if components[to].size &lt; components[from].size

  components[from].each do |i|
    component_index[i] = to
  end
  components[to].merge components[from]
end


In case memory is a problem, you probably don't need to store the sets themselves, but only their
size, since you know that they will never overlap, and that the size of the merged set is always
the sum of the sizes of the 2 sets. But by doing so you have to loop through all nodes when
updating components, which can be much longer.

Building Cost

Last thing to change: how we compute the cost of the solution. We will need the final connected
components. This can be extracted like:

final_component_index = component_index.uniq


Then the MST cost would be

  roads_cost = c_road * final_component_index.inject(0) { |sum, x| components[x].size - 1 + sum }


And the final cost

  final_component_index.size * c_lib + roads_cost