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:

The search continues from the original start point until all reachable vertices are found, and if there are undiscovered vertices, the search continues with the one with the lowest number as the new start point.

I overlooked it.

4. Undiscovered apex

This problem is about $ 1 \ leq n \ leq 100 $, so I dealt with it in a loop from 1 to 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

If ʻi is not in visited`, it is an undiscovered vertex and the search continues.

5. Example answer

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])

I was able to AC </ font> without any problems. It may be a lot of wasteful code, but I personally think it was easy to understand: thumbsup: If you have any code improvements, please leave a comment! !!

in conclusion

This question was for practicing depth-first search, as the title says Depth First Search. It's the basic of the basics!

Personally, I feel that depth-first search is easy to understand when implementing using a stack. Of course, I think it is necessary to use recursion properly depending on the problem.

Competitive programming has different approaches to one problem, so increasing withdrawals is essential. I wish I could continue to increase it little by little ...

By the way, I'm a chick just starting to participate in the contest: hatched_chick: https://atcoder.jp/users/ajim

Recommended Posts