Jan 2020
1 / 2
Jan 2020
Jan 2020
potato_pc1
Jan '20
1

I’m new to SPOJ, and is practically using this site’s problems to practice my Python.
I tried LASTSHOT and got TLE every time. I don’t quite understand the reason, my code has a time complexity of n^2,but most of the accepted solutions in c++ have a complexity of n^2. Any optimization?
Any idea, about this?

from collections import defaultdict

def dfs(node, v, c, a):
v[node] = True
c = 1
for i in a[node]:
if not v[i]:
c += dfs(i, v, c, a)
return c

n, m = [int(i) for i in input().split()]
a_l = defaultdict(list)
l = []
for i in range(m):
a1, a2 = [int(i) for i in input().split()]
a_l[a1-1].append(a2-1)
for j in range(n):
visited = [False]*n
c = 0
x = dfs(j, visited, c, a_l)
l.append(x)
print(max(l))

  • created

    Jan '20

  • last reply

    Jan '20
  • 1

    reply

  • 631

    views

  • 2

    users

  • 1

    link

simes
Jan '20

Welcome to SPOJ!

I’m not a python programmer, and have rarely used it, so I may be talking nonsense.

LASTSHOT1 has a range of time limits between 0.1 and 1 second. That lower end is always going to cause problems for Python with its relatively slow startup time. It may that you need to choose another language.

Or, I’m sure Python offers many alternative ways of doing this. They may not be as neat, but they may be faster - experiment a little. Make a reasonable size data set and do some timings.

btw, full marks for pasting the code in a format that retains the indentation, many people don’t manage that. But an image is really inconvenient if I needed to run your code to test it.

You can paste the code and retain the indentation by indenting the code with four spaces, like this

for i in range(n):
    doSomething(i)