Es muss nicht auf die Euler-Tour beschränkt sein, aber nicht rekursiv DFS zu schreiben ist ein bisschen schwierig, nicht wahr? Es ist meine eigene Art zu schreiben. Wenn Sie die Richtlinie zuerst schreiben, sieht sie folgendermaßen aus.
Ich werde ein wenig über ABC 163-F schreiben.
$ N $ Angenommen, ein Baum von Eckpunkten wird durch eine Kante angegeben. Wenn es 1-indiziert ist, subtrahieren Sie bitte $ 1 $ auf dem Weg.
test.py
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
# x, y = x-1, y-1
X[x].append(y)
X[y].append(x)
Schreiben wir es zunächst rekursiv. ET ist eine Abkürzung für Euler Tour. Bei der Verarbeitung jedes Scheitelpunkts
Du solltest es tun.
test.py
done = [0] * N
ET = []
def dfs(i):
done[i] = 1
ET.append(i) #Zum Start zur Liste hinzufügen
for j in X[i]:
if done[j]: continue
dfs(j)
ET.append(i) #Zur Liste hinzufügen, wenn Sie fertig sind
dfs(0)
print("ET =", ET)
Der Code ist prägnant, aber ich möchte Wiederholungen so weit wie möglich vermeiden. Schreiben Sie von hier an das Äquivalent des obigen Codes nicht rekursiv. Die Punkte sind zu Beginn (los) </ font> </ b> und am Ende (los) </ font> < Es ist die Verarbeitung von / b>.
Nicht rekursives DFS sollte in einem Stapel verwaltet werden. Da jedoch sowohl für das Gehen als auch für das Zurückkehren eine Verarbeitung erforderlich ist, legen Sie beim Einlegen jeweils zwei auf. Insbesondere beim Einfügen des i-ten Scheitelpunkts fügen Sie "i" und "~ i" ein ("~ i" ist dasselbe wie "-i-1"). Wenn "~" schwer zu verstehen ist, können Sie mit taple "(1, i)" und "(2, i)" oder "i * 2" und "i * 2 + 1" erstellen. Wie auch immer, fügen Sie einfach die Anfangs- oder Endinformationen und i hinzu, damit sie wiederhergestellt werden können. Alternativ können Sie sie separat als "1", "i", "2", "i" hinzufügen. </ font> Wenn "i" für die Verarbeitung am Ende der Lebensdauer und "~ i" für die Verarbeitung am Ende der Lebensdauer vorgesehen ist, wird es in der Reihenfolge "~ i" → "i" zum Stapel hinzugefügt. Schreiben Sie den "rekursiven" Teil in den Endteil.
Wenn beispielsweise während der Verarbeitung von i j hinzugefügt wird, ändert sich der Stapel wie folgt:
[~i, i] → [~i] → [~i, ~j, j] → [~i, ~j] → [~i] → []
Von rechts betrachtet fühlt es sich an, als würde man das Lebensende verarbeiten, wenn es nicht negativ ist, und die Rückgabe verarbeiten, wenn es negativ ist.
Es sieht so aus, wenn es in Code geschrieben ist.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Wurzel zum Stapel hinzufügen
ET = []
while Q:
i = Q.pop()
if i >= 0: #Bearbeitung des Endes
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Fügen Sie dem Stapel die Rückgabeverarbeitung hinzu
Q.append(a) #Fügen Sie dem Stapel die Verarbeitung am Ende der Lebensdauer hinzu
else: #Rückgabeverarbeitung
ET.append(~i)
return ET
print(EulerTour(N, X, 0))
Wenn danach andere Prozesse vorhanden sind, können Sie die Prozesse hinzufügen, damit sie ordnungsgemäß ausgeführt und zurückgegeben werden.
Übrigens, in der Euler-Tour habe ich gesagt, dass ich es auf dem Weg hin und her zur Liste hinzufügen würde, aber Ich glaube nicht, dass Sie den Rückweg oft brauchen </ font>? Ich glaube schon. In einem solchen Fall müssen Sie nicht beide erzwingen. Alles, was Sie tun müssen, ist, die Hin- und Rückfahrt nicht mehr hinzuzufügen. Es wird empfohlen, da der Code sauber ist, leicht zu debuggen ist und die Verarbeitung beschleunigt wird.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Wurzel zum Stapel hinzufügen
ET = []
while Q:
i = Q.pop()
if i >= 0: #Bearbeitung des Endes
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Fügen Sie dem Stapel die Rückgabeverarbeitung hinzu
Q.append(a) #Fügen Sie dem Stapel die Verarbeitung am Ende der Lebensdauer hinzu
else: #Rückgabeverarbeitung
pass # ET.append(~i) #← Wenn Sie dies nicht verwenden, können Sie es entfernen
return ET
print(EulerTour(N, X, 0))
Sie möchten eine Startnummer und eine Endnummer für jeden Scheitelpunkt. Ich habe alles andere eingegeben. Es ist meine Bibliothek, einschließlich Kommentare.
test.py
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
X[x].append(y)
X[y].append(x)
def EulerTour(n, X, i0):
#X kann zerstört werden, um X und P zu machen
P = [-1] * n
Q = [~i0, i0]
ct = -1
ET = []
ET1 = [0] * n
ET2 = [0] * n
DE = [0] * n
de = -1
while Q:
i = Q.pop()
if i < 0:
#↓ Verwenden Sie diese Option, wenn Sie Zahlen für die Rückgabe hinzufügen
# ct += 1
#↓ Verwenden Sie diese Option, wenn Sie die Rückgabe in ET einfügen möchten
# ET.append(P[~i])
ET2[~i] = ct
de -= 1
continue
if i >= 0:
ET.append(i)
ct += 1
if ET1[i] == 0: ET1[i] = ct
de += 1
DE[i] = de
for a in X[i][::-1]:
if a != P[i]:
P[a] = i
for k in range(len(X[a])):
if X[a][k] == i:
del X[a][k]
break
Q.append(~a)
Q.append(a)
return (ET, ET1, ET2)
ET, ET1, ET2 = EulerTour(N, X, 0)
print("ET =", ET) #I-te Scheitelpunktnummer des Pfades
print("ET1 =", ET1) # Start
print("ET2 =", ET2) # End
Die Start- und Endnummern jedes Scheitelpunkts werden in "ET1" bzw. "ET2" gespeichert.
DE ist Tiefe, die Tiefe. Wenn Sie dies nicht benötigen, können Sie es löschen.
ABC 163-F
Das Problem ist hier
Wenn Sie die Farbe i betrachten, teilen Sie die nicht mit i gemalten Eckpunkte in Verbindungskomponenten. Wenn die Anzahl jeder Komponente $ x $ beträgt, ermitteln Sie die Summe von $ x (x + 1) / 2 $. ist. Schauen Sie sich die Euler-Tour der Reihe nach an und subtrahieren Sie an jedem Scheitelpunkt die Anzahl derjenigen, die bereits unter diesem Scheitelpunkt verwendet haben (schlechtes Japanisch). Einzelheiten finden Sie im Code.
Sie müssen sich nicht die Details ansehen (weil es kein hübscher Code ist), aber es reicht aus, wenn Sie wissen, dass Sie die Verarbeitung in "Going" und "Going" umwandeln können.
Recommended Posts