Saving the Universe - Code Jam 2008 Qualification problem A
#Feels wrong having four prints

Indeed.

    print "Case %d: %d" % (i, solve(inFile))


is good enough.
#Feels wrong but queue=set(temp) doesn't work

Yes. The set constructor requires an iterable. Consider queue = set([temp]).
#Feels wrong doing this one at a time

I don't think you can do anything about this. As a side note, what really feels wrong is that these parts of the test cases are totally irrelevant to the solution; only the number of engines really matter. Kudos for realizing this.

As usual, a no naked loops principle dictates to factor this loop out into a function:

    def discard_names_as_useless(inFile, S):

Naming

Q and S only make sense for those who read the problem statement. Consider instead something like number_of_queries and number_of_engines.
import fileinput 

Using fileinput seems like an overkill. It is only useful if you need to process multiple files in a row. In this case an unadorned raw_input() would work just fine.
PS

Be careful describing the problem statement. Your description 


  The program should return the minimum number of batches required.


raised an immediate red flag: this code must be off-by-one. I had to read the original to realize that they ask for the number of _engine switches__.