[GO] Depth-first search using stack in Python

Introduction

I recently started competitive programming and am addicted to its depth. But in competitive programming, if you don't know the algorithm, you'll be completely sick from a certain level: disappointed_relieved:

So, Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ] "[100 past questions that beginners and intermediates should solve by field](https://qiita.com/e869120/items/eb50fdaece12be418faa#2 -3-% E5% 88% 86% E9% 87% 8E% E5% 88% A5% E5% 88% 9D% E4% B8% AD% E7% B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E% BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) ”is being solved little by little these days!

Depth-first search

What I was interested in this time was depth-first search. Until now, it was implemented recursively, but when I looked it up, there is also a way to use the stack, so I will implement it using the stack.

example

Depth-first search of 100 past questions, which is written as a basic problem, ALDS1_11_B Solve. The difficult point of this problem was to output the discovery time and the search completion time. (Because I'm still a beginner ...)

1. Input

The first line has $ n $ vertices, the following $ n $ line, Given the number of vertices $ u $, the number of adjacent vertices $ k $, and the number of adjacent vertices $ v_1 \ v_2 \ ... \ v_k $.

n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

A list of 0s is added first to align the vertex numbers and index numbers. (It is not absolutely necessary.)

2. Required variables

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)

Stack, which acts as a stack (it seems that you can use deque of collections. This time, it is implemented in a list.) Keep a record of the vertices you have already visited visited Time representing the time List of vertex discovery times d List of vertex completion times f (D and f are also set to n + 1 because they have the same index number.)

3. Search part

while stack:
    s = stack[-1]             # (1)Vertices to explore
    k = ukv[s][1]             # (2)Number of vertices adjacent to s
    if k == 0:                # (6)Since there are no adjacent vertices from s,
        stack.pop()           #Remove s from stack
        time += 1
        f[s] = time           # (7)Time when the search for s was completed
    else:
        v = ukv[s].pop(2)     # (3)The vertex with the smallest number adjacent to s
        ukv[s][1] -= 1        # (4)Reduce the number of adjacent vertices from s
        if v not in visited:
            stack.append(v)
            visited.append(v)
            time += 1
            d[v] = time       # (5)The time when v was discovered

The point is not to pop () from stack when defining the variable s. At first I tried to manage the discovery time and the completion time in different lists and got lost. We remove s from stack when we come to (6) above. The time when the search for s is complete is when it finds all the vertices reachable from s and returns to s. Therefore, (4) reduces the number of adjacent vertices.

Now you can clear the input example by putting 1 in stack or visited. However, if I submit it as it is, I will get WA </ font> from test case 1:: scream:

for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

        while stack:
            s = stack[-1]
            k = ukv[s][1]
            if k == 0:
                stack.pop()
                time += 1
                f[s] = time
            else:
                ukv[s][1] -= 1
                v = ukv[s].pop(2)
                if v not in visited:
                    stack.append(v)
                    visited.append(v)
                    time += 1
                    d[v] = time

for i in range(1, n + 1):
    print(i, d[i], f[i])