It doesn't have to be limited to Euler Tour, but writing DFS non-recursively is a bit tricky, isn't it? It's my own way of writing. If you write the policy first, it looks like this.
--Writing Euler Tour in non-recursive DFS in Python --DFS manages on the stack --When adding, add two for the way out and one for the way back.
I will write a little about ABC 163-F.
$ N $ Suppose a tree of vertices is given on an edge. If it is 1-indexed, please subtract $ 1 $ on the way.
test.py
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
# x, y = x-1, y-1
X[x].append(y)
X[y].append(x)
First, let's write it recursively. ET is an acronym for Euler Tour. When processing each vertex
You should do it.
test.py
done = [0] * N
ET = []
def dfs(i):
done[i] = 1
ET.append(i) #Add to list at start
for j in X[i]:
if done[j]: continue
dfs(j)
ET.append(i) #Add to list when finished
dfs(0)
print("ET =", ET)
The code is concise, but I want to avoid recursion as much as possible. From here on down, write the equivalent of the above code non-recursively. The points are start (going) </ font> </ b> processing and ending (going) </ font> < The processing of / b>.
Non-recursive DFS should be managed on the stack.
However, since processing is required for both going and returning, put two each when putting them on the stack. Specifically, when inserting the i-th vertex, insert ʻiand~ i ( ~ iis the same as-i-1). If "~" is difficult to understand, you can use tuples such as (1, i)and(2, i), or ʻi * 2 and ʻi * 2 + 1. Anyway, just add the beginning or ending information and i so that it can be restored. <font color = "a0a0a0"> Alternatively, you can add them separately as 1, ʻi, 2, ʻi. </ font> If ʻi is used for the destination processing and ~ i is used for the return processing, the stack is added in the order of ~ i → ʻi`. Write the "recursive" part in the end part.
For example, if j is added while processing i, the stack changes as follows:
[~i, i] → [~i] → [~i, ~j, j] → [~i, ~j] → [~i] → []
Looking from the right, it feels like processing the end-of-life if it is non-negative, and processing the return if it is negative.
It looks like this when written in code.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Add roots to the stack
ET = []
while Q:
i = Q.pop()
if i >= 0: #Processing of the end
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Add return processing to the stack
Q.append(a) #Add end-of-life processing to the stack
else: #Return processing
ET.append(~i)
return ET
print(EulerTour(N, X, 0))
After that, if there are other processes, you can add the processes to make them go and return appropriately.
By the way, Euler Tour said that it will be added to the list on the way back and forth, but You often don't need the way back </ font>, don't you think? I think so. In such a case, you don't have to force both. All you have to do is stop adding the return trip. It is recommended because the code is clean, it is easy to debug, and the processing is speeded up.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Add roots to the stack
ET = []
while Q:
i = Q.pop()
if i >= 0: #Processing of the end
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Add return processing to the stack
Q.append(a) #Add end-of-life processing to the stack
else: #Return processing
pass # ET.append(~i) #← If you don't use this, you can remove it
return ET
print(EulerTour(N, X, 0))
You want a start number and an end number for each vertex. I've put in everything else. It's my library as it is, including comments.
test.py
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
X[x].append(y)
X[y].append(x)
def EulerTour(n, X, i0):
#X can be destroyed to make X and P
P = [-1] * n
Q = [~i0, i0]
ct = -1
ET = []
ET1 = [0] * n
ET2 = [0] * n
DE = [0] * n
de = -1
while Q:
i = Q.pop()
if i < 0:
#↓ Use this when adding numbers for return
# ct += 1
#↓ Use this if you want to put the return in ET
# ET.append(P[~i])
ET2[~i] = ct
de -= 1
continue
if i >= 0:
ET.append(i)
ct += 1
if ET1[i] == 0: ET1[i] = ct
de += 1
DE[i] = de
for a in X[i][::-1]:
if a != P[i]:
P[a] = i
for k in range(len(X[a])):
if X[a][k] == i:
del X[a][k]
break
Q.append(~a)
Q.append(a)
return (ET, ET1, ET2)
ET, ET1, ET2 = EulerTour(N, X, 0)
print("ET =", ET) #I-th vertex number of Path
print("ET1 =", ET1) # Start
print("ET2 =", ET2) # End
The start and end numbers of each vertex are stored in ʻET1 and ʻET2, respectively.
DE is depth, the depth. If you don't need this, you can delete it.
ABC 163-F
The problem is here
When looking at the color i, divide the vertices not painted with i into connected components, and if the number of each component is $ x $, you can find the sum of $ x (x + 1) / 2 $. is. Look at the Euler Tour in order, and at each vertex, subtract the number of guys already used below that vertex (bad Japanese). See the code for details.
You don't have to look at the details (because it's not pretty code), but it's enough if you know that you can put the processing into "going" and "going".
April 21, 2020: Posted April 21, 2020 (same day): Added about "method without returning home" and "ABC 163-F"
Recommended Posts