Il n'est pas nécessaire de se limiter à Euler Tour, mais écrire DFS de manière non récursive est un peu délicat, n'est-ce pas? C'est ma propre façon d'écrire. Si vous écrivez d'abord la politique, elle ressemble à ceci.
J'écrirai un peu sur ABC 163-F.
$ N $ Supposons qu'un arbre de sommets soit donné par une arête. S'il est indexé à 1, veuillez soustraire 1 $ en cours de route.
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)
Tout d'abord, écrivons-le récursivement. ET est un acronyme pour Euler Tour. Lors du traitement de chaque sommet
Tu devrais le faire.
test.py
done = [0] * N
ET = []
def dfs(i):
done[i] = 1
ET.append(i) #Ajouter à la liste au début
for j in X[i]:
if done[j]: continue
dfs(j)
ET.append(i) #Ajouter à la liste une fois terminé
dfs(0)
print("ET =", ET)
Le code est concis, mais je veux éviter autant que possible la récurrence. À partir de là, écrivez l'équivalent du code ci-dessus de manière non récursive. Les points sont au début (en cours) </ font> </ b> le traitement et à la fin (en cours) </ font> < C'est le traitement de / b>.
Les DFS non récursifs doivent être gérés dans une pile.
Cependant, comme le traitement est nécessaire à la fois pour aller et pour revenir, mettez-en deux chacun lors de leur mise dans la pile. Plus précisément, lors de l'insertion du i-ème sommet, insérez «i» et «~ i» («~ i» est identique à «-i-1»). Si «~» est difficile à comprendre, vous pouvez utiliser taple pour créer «(1, i)» et «(2, i)», ou «i * 2» et «i * 2 + 1». Quoi qu'il en soit, ajoutez simplement les informations de début ou de fin et i pour qu'elles puissent être restaurées. Vous pouvez également les ajouter séparément en tant que «1», «i», «2», «i». </ font>
Si ʻiest utilisé pour le traitement de destination et que~ i est utilisé pour le traitement de retour, la pile est ajoutée dans l'ordre de ~ i → ʻi. Écrivez la partie "récursive" dans la partie finale.
Par exemple, si j est ajouté lors du traitement de i, la pile change comme suit:
[~i, i] → [~i] → [~i, ~j, j] → [~i, ~j] → [~i] → []
En regardant de droite, on a l'impression de traiter la fin de vie si elle est non négative et de traiter le retour si elle est négative.
Cela ressemble à ceci lorsqu'il est écrit dans le code.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Ajouter la racine à la pile
ET = []
while Q:
i = Q.pop()
if i >= 0: #Traitement de la fin
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Ajouter le traitement des retours à la pile
Q.append(a) #Ajouter un traitement de fin de vie à la pile
else: #Traitement des retours
ET.append(~i)
return ET
print(EulerTour(N, X, 0))
Après cela, s'il existe d'autres processus, vous pouvez ajouter les processus pour les faire aller et revenir de manière appropriée.
Au fait, dans le Euler Tour, j'ai dit que je l'ajouterais à la liste en allant et en revenant, mais Je ne pense pas que vous ayez souvent besoin du retour </ font>? Je le pense. Dans un tel cas, vous n'avez pas à forcer les deux. Tout ce que vous avez à faire est d'arrêter d'ajouter le voyage de retour. Il est recommandé car le code est propre, il est facile à déboguer et le traitement est accéléré.
test.py
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] #Ajouter la racine à la pile
ET = []
while Q:
i = Q.pop()
if i >= 0: #Traitement de la fin
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) #Ajouter le traitement des retours à la pile
Q.append(a) #Ajouter un traitement de fin de vie à la pile
else: #Traitement des retours
pass # ET.append(~i) #← Si vous ne l'utilisez pas, vous pouvez le supprimer
return ET
print(EulerTour(N, X, 0))
Vous voulez un numéro de début et un numéro de fin pour chaque sommet. J'ai mis tout le reste. C'est ma bibliothèque telle qu'elle est, y compris les commentaires.
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 peut être détruit pour faire X et P
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:
#↓ Utilisez ceci lors de l'ajout de numéros pour le retour
# ct += 1
#↓ Utilisez ceci si vous voulez mettre le retour dans ET
# 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) #Numéro I-ième sommet du chemin
print("ET1 =", ET1) # Start
print("ET2 =", ET2) # End
ʻET1 et ʻET2 stockent respectivement les numéros de début et de fin de chaque sommet.
«DE» est la profondeur, la profondeur. Si vous n'en avez pas besoin, vous pouvez le supprimer.
ABC 163-F
Le problème se trouve ici
Lorsque vous regardez la couleur i, divisez les sommets non peints avec i en composants de connexion, et si le nombre de chaque composant est $ x $, trouvez la somme de $ x (x + 1) / 2 $. est. Regardez le tour d'Euler dans l'ordre, et à chaque sommet, soustrayez le nombre de ceux qui l'ont déjà utilisé en dessous de ce sommet (mauvais japonais). Voir le code pour plus de détails.
Vous n'avez pas besoin de regarder les détails (parce que ce n'est pas non plus un code propre), mais c'est suffisant si vous savez que vous pouvez mettre le traitement en "va" et "en cours".
21 avril 2020: Publié 21 avril 2020 (même jour): Ajout de "méthode sans retour à la maison" et "ABC 163-F"
Recommended Posts