Hi fellows!
Who got AC TDBFS - "Searching The Graph" - with Python?
I myself got it in C, but the same code in Python gives TLE...
I'm new in Python, so please help me - give me some hints as to how speed up python codes.
Here's my code:
[code]#!/usr/bin/env python
import sys,string
def dfs(u):
visited[u] = counter
print u,
for i in range(degree[u]):
v = adj[(u,i)]
if visited[v] != counter:
dfs(v)
class queue:
def init(self):
(self.q,self.head,self.tail) = ({},0,-1)
def enqueue(self,u):
self.tail += 1
self.q[self.tail] = u
print u,
def dequeue(self):
v = self.q[self.head]
self.head += 1
return v
def empty(self):
return self.head > self.tail
def bfs(u):
(q,tail,head) = ({},-1,0)
tail += 1
q[tail] = u
"""
Q = queue()
Q.init()
Q.enqueue(u)
"""
visited[u] = counter
print u,
while tail >= head:
"""
x = Q.dequeue()
"""
x = q[head]
head += 1
for i in range(degree[x]):
y = adj[(x,i)]
if visited[y] != counter:
#Q.enqueue(y)
tail += 1
q[tail] = y
visited[y] = counter
print y,
if name == 'main':
degree,adj = {},{}
visited = {}
counter = 0
#sys.stdin = open('TDBFS.txt','r')
for t in range(int(sys.stdin.readline())):
print "graph %d" % (t+1)
for j in range(int(sys.stdin.readline())):
s = list(string.split(sys.stdin.readline()))
u = int(s[0])
degree[u],visited[u]= 0,counter
#assert int(s[1]) == len(s) - 2
L = len(s)
for i in range(2,L):
v = int(s[i])
adj[(u,degree[u])] = v
degree[u] += 1
#assert degree[u] == int(s[1])
(start,f) = string.split(sys.stdin.readline())
(start,f) = int(start),int(f)
while start or f:
counter += 1
if not f:
dfs(start)
else:
bfs(start)
print
(start,f) = string.split(sys.stdin.readline())
(start,f) = int(start),int(f)[/code]
Thanks in advance
