ARC037 Baum testet höflich mit rekursiver Python-Funktion

Dies ist ein Artikel für Anfänger

Dieser Artikel wurde von Anfängern von Wettkampfprofis verfasst, um ihr Verständnis des Studiums zu vertiefen, und es ist ein Artikel, der in Details zerquetscht wurde. Ich habe es in der Hoffnung geschrieben, dass es denjenigen helfen würde, die neu im selben Wettbewerb sind. Darüber hinaus basiert der Antwortcode für diesen Artikel auf dem Artikel Arimoto in Python (Anfänger). Ich bin.

ARC037 Baum Test

Bitte überprüfen Sie die Problemstellung unter hier. Zunächst werde ich den Antwortcode einführen.

python.py

def dfs(now, prev):
    global flag
    #Schleife, indem Sie die Scheitelpunkte, die von den aktuellen Scheitelpunkten ausgehen können, in die nächste Reihenfolge bringen
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Geschlossen, wenn in der Vergangenheit besucht
                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)

#Hast du besucht
memo = [False for i in range(n)]

ans = 0
#Schleife die Eckpunkte
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #Wenn es keine gesperrte Straße gibt, ist es ein Baum
            ans += 1
print(ans)

Ich werde diesen Antwortcode separat erklären. Zunächst erkläre ich den Teil, der die Stellen, die von jedem Scheitelpunkt verschoben werden können, als Liste zusammenfasst.

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 #Um die Listennummer mit der Nummer der Scheitelpunktposition abzugleichen
    v -= 1
    g[u].append(v)
    g[v].append(u)

Persönlich kann ich das noch nicht, also stolpere ich ... Wenn zwei Zahlenpaare (u, v) in m Paaren übergeben werden, ist der Ort, an dem Sie sich bewegen können, wenn der aktuelle Ort u ist, indem Sie die Zahl links als aktuellen Ort und die Zahl rechts als beweglichen Ort sehen g [ Es wird angenommen, dass es in u] gespeichert ist. Als nächstes konzentrieren wir uns auf den rekursiven Funktionsteil.

saiki.py

def dfs(now, prev):
    global flag  #Weil die Änderung des Flags innerhalb der Funktion außerhalb der Funktion angewendet wird.
    #Schleife, indem Sie die Scheitelpunkte, die von den aktuellen Scheitelpunkten ausgehen können, in die nächste Reihenfolge bringen
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Geschlossen, wenn in der Vergangenheit besucht
                flag = False
            else:
                memo[next] = True
                dfs(next, now)

In diesem Problem müssen wir feststellen, ob der Graph, der die Position enthält, an der die rekursive Funktion aufgerufen wurde, ein Baum ist. Verwenden Sie daher zuerst das Flag, um festzustellen, ob die Straße gesperrt ist, wenn sie wahr ist, und geschlossen, wenn sie falsch ist.

Als nächstes werde ich erklären, was wir mit einer rekursiven Funktion machen. In der rekursiven Funktion wird der aktuelle Speicherort jetzt angegeben, und die nächste Verschiebungsoption g [jetzt], die in now enthalten ist, wird next zugewiesen, um zu suchen. Im Gegensatz zu prev wird next, wenn next ein Ort ist, der noch nie besucht wurde, next dem next zugewiesen, um an einem tieferen Ort zu suchen. (Kompliziert) Wenn Sie einen neuen Ort besuchen, setzen Sie memo [next] = True als Trace. Wenn das von next angegebene Memo [next] bereits True ist, ist dies die zweite Suche, sodass es als geschlossen beurteilt wird.

Abschließend werde ich den Aufrufteil der rekursiven Funktion erläutern.

saikiyobidasi.py

ans = 0
#Schleife die Eckpunkte
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #Wenn es keine gesperrte Straße gibt, ist es ein Baum
            ans += 1

Der Teil des rekursiven Funktionsaufrufs ist einfach. Ans wird verwendet, um zu zählen, wie oft festgestellt wurde, dass es sich um einen Baum handelt. Wenn Sie in der for-Anweisung noch nie n Eckpunkte besucht haben, starten Sie die Baumbeurteilung mit flag = True und rufen Sie die rekursive Funktion auf. Wenn flag = True ist, nachdem die Verarbeitung durch die rekursive Funktion abgeschlossen ist, wird ans um +1 erhöht.

Dies ist das Ende der Erklärung von ARC037. Persönlich war dieses Problem schwierig, wenn es darum ging, der Tiefe des Ameisenbuchs Vorrang einzuräumen. Deshalb versuchte ich, mein Verständnis zu verstehen, indem ich es ausführlich erklärte. Bitte weisen Sie auf Fehler hin.