[GO] Suche nach Tiefenpriorität mit Stack in Python

Einführung

Ich habe vor kurzem angefangen, wettbewerbsfähig zu programmieren und bin süchtig nach seiner Tiefe. Wenn Sie jedoch bei der Wettbewerbsprogrammierung den Algorithmus nicht kennen, sind Sie ab einem bestimmten Level völlig krank: enttäuscht_relieved:

Also, Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Intermediate Edition: Aim for Light Blue Coder! ] "[100 frühere Fragen, die Anfänger und Fortgeschrittene nach Feld lösen sollten](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) ”wird heutzutage nach und nach gelöst!

Tiefenprioritätssuche

Was mich diesmal interessierte, war die Tiefenprioritätssuche. Bisher wurde es rekursiv implementiert, aber als ich es nachgeschlagen habe, gibt es auch eine Möglichkeit, den Stapel zu verwenden, sodass ich ihn mithilfe des Stapels implementieren werde.

Beispiel

ALDS1_11_B, das als Grundproblem geschrieben wurde, eine Tiefenprioritätssuche von 100 vergangenen Fragen Ich werde es lösen. Der schwierige Punkt dieses Problems bestand darin, die Erkennungszeit und die Suchabschlusszeit auszugeben. (Weil ich noch ein Anfänger bin ...)

1. Eingabe

Die erste Zeile hat die Anzahl der Eckpunkte $ n $, die folgende Zeile $ n $, Angesichts der Anzahl der Eckpunkte $ u $, der Anzahl benachbarter Eckpunkte $ k $ und der Anzahl benachbarter Eckpunkte $ v_1 \ v_2 \ ... \ v_k $.

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

Zuerst wird eine Liste mit Nullen hinzugefügt, um die Scheitelpunktnummern und Indexnummern auszurichten. (Es ist nicht unbedingt notwendig.)

2. Erforderliche Variablen

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

"Stapel", der als Stapel fungiert (Es scheint, dass Sie "deque" von "Sammlungen" verwenden können. Dieses Mal ist es in einer Liste implementiert.) Notieren Sie sich die Gipfel, die Sie bereits besucht haben "Zeit" steht für Zeit Liste der Spitzenentdeckungszeiten d Liste der Fertigstellungszeiten der Eckpunkte f (D und f werden ebenfalls auf n + 1 gesetzt, da sie dieselbe Indexnummer haben.)

3. Teil suchen

while stack:
    s = stack[-1]             # (1)Top zu erkunden
    k = ukv[s][1]             # (2)Anzahl benachbarter Eckpunkte von s
    if k == 0:                # (6)Da gibt es keine benachbarten Eckpunkte von s
        stack.pop()           #Entfernen Sie s vom Stapel
        time += 1
        f[s] = time           # (7)Zeitpunkt, zu dem die Suche nach s abgeschlossen wurde
    else:
        v = ukv[s].pop(2)     # (3)Der Scheitelpunkt mit der kleinsten Zahl neben s
        ukv[s][1] -= 1        # (4)Reduzieren Sie die Anzahl benachbarter Eckpunkte von s
        if v not in visited:
            stack.append(v)
            visited.append(v)
            time += 1
            d[v] = time       # (5)Die Zeit, als v entdeckt wurde

Bei der Definition der Variablen "s" geht es nicht darum, "pop ()" vom "Stapel" zu entfernen. Zuerst habe ich versucht, die Erkennungszeit und die Abschlusszeit in verschiedenen Listen zu verwalten und bin verloren gegangen. Das s wird aus dem Stapel entfernt, wenn es um (6) oben geht. Wenn die Suche nach "s" abgeschlossen ist, werden alle von "s" erreichbaren Scheitelpunkte gefunden und zu "s" zurückgekehrt. Daher reduziert (4) die Anzahl benachbarter Eckpunkte.

Jetzt können Sie das Eingabebeispiel löschen, indem Sie "1" in "Stapel" oder "besucht" setzen. Wenn ich es jedoch so einreiche, wie es ist, erhalte ich WA </ font> aus Testfall 1 :: schreien:

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