I've written this in response to this comment when I was solving a different problem.

Summary: You got weight: - Lookup time (in graph traversals) - str to int conversion -> reading the graph - int to str conversion -> output the graph ___

Take this problem for example, it has an awfully big input and also a big output. (for big I mean ~10^5 ints)

We have more than 200000 numbers. (when N=10^5 and M=10^5)

I`ve used an EC2 small machine to do the timings and they were quite close to the timus judge's output. EC2 seems slower than timus.

Here's some timings for the input with max N and M:

Using a list for the graph (int indexed):

from sys import stdin
from itertools import izip, islice

tkns = iter(map(int, stdin.read().split()))
n,m = int(tkns.next()), int(tkns.next())
graph = [[] for i in xrange(n+1)]
for u,v in islice(izip(tkns,tkns),m):
        graph[u].append(v)
        graph[v].append(u)

In 10 runs the min,max time where: 0.726s and 0m0.814s

Using a dict for the graph (str indexed):

from sys import stdin
from itertools import izip, islice

tkns = iter(stdin.read().split())
n,m = int(tkns.next()), int(tkns.next())
graph = {str(i): [] for i in xrange(1,n+1)}
for u,v in islice(izip(tkns,tkns),m):
        graph[u].append(v)
        graph[v].append(u)

In 10 runs the min,max time where: 0.582s and 0m0.652s

The time limit for this problem was 1s, my solution took 0.717 and is currently the only python solution. The "same" solution in C took 0.072s.

Should we ALWAYS use dict based graphs?

NO, even though the access time for list is faster, if you traverse the graph a lot and you have many edges or vertices you probably should pay the price of 0.1-0.2s (which is not cheap). Here's a problem (timus1389-roadworks) which I couldn`t use a dict based graph to AC it. The solution is in the post: Maximal Matching in a Tree.

Keep in mind that if you have to cast int to str for output (in this problem you had to output lots of stuff) you have to pay this price too. (and it is not cheap)

Observations: - Casting str to int is not cheap - str to int and int to str DO NOT cost the same.

Related SO: http://stackoverflow.com/questions/11687183/more-efficient-to-convert-string-to-int-or-inverse