ARC037 Baum test politely with Python recursive function

This is an article for beginners

This article was written by beginners of competition professionals to deepen their understanding of studying, and it is an article that has been crushed into details. I wrote it in the hope that it would help those who are new to the same competition pro. In addition, the answer code for this article is based on the article Ant book in Python (beginner's edition). I am.

ARC037 Baum test

Please check the problem statement at here. First of all, I will introduce the answer code.

python.py

def dfs(now, prev):
    global flag
    #Loop by putting the vertices that can be reached from the current vertex into next in order
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Closed if visited in the past
                flag = False
            else:
                memo[next] = True
                dfs(next, now)


n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#Have you visited
memo = [False for i in range(n)]

ans = 0
#Loop the vertices
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #If there is no cycle, it is a tree
            ans += 1
print(ans)

I will explain this answer code separately. First, I will explain the part that summarizes the places that can be moved from each vertex as a list.

list.py

n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1 #To match the number of the list with the number of the position of the vertex
    v -= 1
    g[u].append(v)
    g[v].append(u)

Personally, I can't do this yet, so I'm stumbling ... When m pairs of two numbers (u, v) are passed, the place where you can move when the current location is u is g [ It is thought that it is stored in u]. Next, let's focus on the recursive function part.

saiki.py

def dfs(now, prev):
    global flag  #Because the change of flag inside the function is applied outside the function.
    #Loop by putting the vertices that can be reached from the current vertex into next in order
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Closed if visited in the past
                flag = False
            else:
                memo[next] = True
                dfs(next, now)

In this problem we need to determine if the graph containing the position where the recursive function was called is a tree. Therefore, first use flag to determine that it is a tree if it is True and that it is a cycle if it is False.

Next, I will explain what we are doing with the recursive function. In the recursive function, the current location is specified by now, and the next move option g [now] included in now is assigned to next in order to search. Unlike prev, when next is a place that has never been visited, next is assigned to the next now to search in a deeper place. (Complicated) When you visit a new place, set memo [next] = True as a trace. Also, if memo [next] specified by next is already True, it will be the second search, so it will be judged as a cycle.

Finally, I will explain the call part of the recursive function.

saikiyobidasi.py

ans = 0
#Loop the vertices
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #If there is no cycle, it is a tree
            ans += 1

The recursive function call part is simple. Ans is used to count the number of times it is determined to be a tree. In the for statement, the tree judgment is started with flag = True and the recursive function is called when the n vertices have never been visited. If flag = True after the processing by the recursive function is finished, ans is incremented by 1.

This is the end of the explanation of ARC037. Personally, this problem was difficult when I gave priority to the depth of the ant book, so I tried to understand my understanding by explaining it in detail. Please point out any mistakes.