Recherche de priorité de profondeur à l'aide de la pile en Python

introduction

J'ai récemment commencé la programmation compétitive et je suis accro à sa profondeur. Mais dans la programmation compétitive, si vous ne connaissez pas l'algorithme, vous serez complètement malade d'un certain niveau: déçu_relieved:

Donc, Directives pour améliorer AtCoder, un professionnel de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue Coder! ] "[100 questions passées que les débutants et les intermédiaires devraient résoudre par champ](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) »se résout petit à petit ces jours-ci!

Recherche de priorité de profondeur

Ce qui m'intéressait cette fois, c'était la recherche de priorité en profondeur. Jusqu'à présent, il était implémenté de manière récursive, mais quand je l'ai recherché, il y a aussi un moyen d'utiliser la pile, donc je vais l'implémenter en utilisant la pile.

exemple

ALDS1_11_B, qui est écrit comme un problème de base, une recherche prioritaire approfondie de 100 questions passées Je vais le résoudre. Le point difficile de ce problème était de sortir l'heure de découverte et l'heure de fin de la recherche. (Parce que je suis encore un débutant ...)

1. Entrée

La première ligne a le nombre de sommets $ n $, la ligne $ n $ suivante, Étant donné le nombre de sommets $ u $, le nombre de sommets adjacents $ k $, et le nombre de sommets adjacents $ v_1 \ v_2 \ ... \ v_k $.

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

Une liste de 0 est ajoutée en premier pour aligner les numéros de sommets et les numéros d'index. (Ce n'est pas absolument nécessaire.)

2. Variables requises

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

Stack, qui agit comme une pile (Il semble que vous puissiez utiliser deque de collections. Cette fois, il est implémenté dans une liste.) Gardez une trace des pics que vous avez déjà visités "Temps" représentant le temps Liste des heures de pointe de découverte d Liste des temps de complétion des sommets f («D» et «f» sont également définis sur «n + 1» car ils ont le même numéro d'index.)

3. Rechercher une partie

while stack:
    s = stack[-1]             # (1)Top à explorer
    k = ukv[s][1]             # (2)Nombre de sommets adjacents de s
    if k == 0:                # (6)Puisqu'il n'y a pas de sommets adjacents de s
        stack.pop()           #Retirer les s de la pile
        time += 1
        f[s] = time           # (7)Heure à laquelle la recherche de s a été terminée
    else:
        v = ukv[s].pop(2)     # (3)Le sommet avec le plus petit nombre adjacent à s
        ukv[s][1] -= 1        # (4)Réduisez le nombre de sommets adjacents de s
        if v not in visited:
            stack.append(v)
            visited.append(v)
            time += 1
            d[v] = time       # (5)Le moment où v a été découvert

Le but n'est pas de pop () from stack lors de la définition de la variable s. Au début, j'ai essayé de gérer le temps de découverte et le temps d'achèvement dans différentes listes et je me suis perdu. Le «s» est supprimé de la «pile» lorsqu'il s'agit de (6) ci-dessus. Le moment où la recherche de «s» est terminée est quand il trouve tous les sommets accessibles à partir de «s» et revient à «s». Par conséquent, (4) réduit le nombre de sommets adjacents.

Maintenant, si vous mettez «1» dans «pile» ou «visité», vous pouvez effacer l'exemple d'entrée. Cependant, si je le soumets tel quel, j'obtiendrai WA </ font> du cas de test 1 :: scream:

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