How do I speed up the recursive process with Python?

The following are the issues.

atcorder270 Problem 3
https://atcoder.jp/contests/abc270/tasks/abc270_c

After submitting it, the test of 10 questions will run out of time.

I am currently working on Python atcorder because I want to gain Python power and I don't want to use any other language.

Is there a way to solve it in python and without running out of time using recursive processing?

import sys
default trace(l,traced,x,y):
    # Investigate all links of nodes
    flg = 0
    for i in l [x]:
        # Add value if not tracked
        if not traced:
            traced.append(i)
            flg+=1
            # Finish when you reach your goal
            if i == y:
                return True
            # Continue tracking except for termination
            if not trace(l,traced,i,y):
                traced.pop()
                flg - = 1
    # node had the following destination
    return flg

default():
    input=sys.stdin.readline

    N, X, Y = map(int, input().split())

    l = [ [ ] for_in range (N+1) ]

    for_in[0]*(N-1):
        A,B = map(int, input().split())
        l[A].append(B)
        l[B].append(A)

    traced = [X]
    
    trace(l,traced,X,Y)
    
    print(''.join([str(s) for inserted]))
resolve()

python algorithm recursion

2022-09-30 20:10

2 Answers

#Add value if not tracked
if not traced:

In this part, it is inefficient to make a linear search every time to see if it has been tracked.This time N reaches up to 200000, so the time of repeated searches on this line is a problem.It is recommended that you keep the flags in an array so that they can be immediately determined if they have been tracked.

2022-09-30 20:10

Code 6 line if not traced: appears to be a bottleneck.

Note:
Python-TimeComplexity

The implementation is simply DFS, but we'll have a list with the information "Which node has this node transitioned from" and update this list at the time of transition. After the search, follow the reverse order (from y) to get the path from x to y.

Implementation examples below.

import sys
sys.setrecursionlimit (10**6)

def dfs(now):
    visited [now] = True
    for nex in graph [ now ]:
        if visited [nex]:
            continue
        from_[nex] = now
        if nex==y:
            return
        dfs(nex)

n, x, y = map(int, input().split())
graph=[] for_in range(n+1)]

for_in range(n-1):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False for_in range(n+1)]
from_=[None for_in range(n+1)]

dfs(x)

htap = [ ]
while is not None:
    htap.append(y)
    y=from_[y]

print(*reversed(htap))

2022-09-30 20:10

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656