ARC037 Baum teste poliment avec la fonction récursive Python

Ceci est un article pour les débutants

Cet article a été rédigé par des professionnels de la compétition débutants pour approfondir leur compréhension de l'étude, et c'est un article qui a été écrasé dans les détails. Je l'ai écrit dans l'espoir qu'il aiderait ceux qui sont nouveaux dans le même concours. De plus, le code de réponse de cet article est basé sur l'article Arimoto in Python (Beginner). Je suis.

Test ARC037 Baum

Veuillez vérifier l'énoncé du problème à ici. Tout d'abord, je présenterai le code de réponse.

python.py

def dfs(now, prev):
    global flag
    #Boucle en mettant les sommets qui peuvent être atteints à partir des sommets courants dans l'ordre suivant
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Fermé si visité dans le passé
                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)

#As tu visité
memo = [False for i in range(n)]

ans = 0
#Boucle les sommets
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #S'il n'y a pas de route fermée, c'est un arbre
            ans += 1
print(ans)

Je vais expliquer ce code de réponse séparément. Tout d'abord, je vais expliquer la partie qui résume les endroits pouvant être déplacés de chaque sommet sous forme de liste.

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 #Pour faire correspondre le numéro de la liste avec le numéro de la position du sommet
    v -= 1
    g[u].append(v)
    g[v].append(u)

Personnellement, je ne peux pas encore faire ça, alors je trébuche ... Lorsque deux paires de nombres (u, v) sont passées par m paires, l'endroit où vous pouvez vous déplacer lorsque l'emplacement actuel est u en voyant le nombre à gauche comme emplacement actuel et le nombre à droite comme lieu mobile est g [ On pense qu'il est stocké dans u]. Ensuite, concentrons-nous sur la partie fonction récursive.

saiki.py

def dfs(now, prev):
    global flag  #Parce que le changement d'indicateur à l'intérieur de la fonction est appliqué en dehors de la fonction.
    #Boucle en mettant les sommets qui peuvent être atteints à partir des sommets courants dans l'ordre suivant
    for next in g[now]:
        if next != prev:
            if memo[next]:
                #Fermé si visité dans le passé
                flag = False
            else:
                memo[next] = True
                dfs(next, now)

Dans ce problème, nous devons déterminer si le graphe contenant la position où la fonction récursive a été appelée est un arbre. Par conséquent, utilisez d'abord l'indicateur pour déterminer que la route est fermée si elle est Vrai et fermée si elle est Faux.

Ensuite, je vais expliquer ce que nous faisons avec une fonction récursive. Dans la fonction récursive, l'emplacement actuel est spécifié maintenant, et l'option de déplacement suivant g [maintenant] incluse dans maintenant est assignée au suivant afin de rechercher. Contrairement à la précédente, quand le prochain est un endroit qui n'a jamais été visité, le suivant est assigné au suivant maintenant pour rechercher dans un endroit plus profond. (Compliqué) Lorsque vous visitez un nouvel endroit, définissez memo [next] = True comme trace. De plus, si memo [next] spécifié par next est déjà True, ce sera la deuxième recherche, donc il sera jugé comme fermé.

Enfin, je vais expliquer la partie appel de la fonction récursive.

saikiyobidasi.py

ans = 0
#Boucle les sommets
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        if flag:
            #S'il n'y a pas de route fermée, c'est un arbre
            ans += 1

La partie de l'appel de fonction récursive est simple. Ans est utilisé pour compter le nombre de fois où il est déterminé comme étant un arbre. Dans l'instruction for, si vous n'avez jamais visité n sommets, démarrez le jugement d'arbre avec flag = True et appelez la fonction récursive. Si flag = True après la fin du traitement par la fonction récursive, ans est incrémenté de +1.

Ceci est la fin de l'explication de ARC037. Personnellement, ce problème était difficile en donnant la priorité à la profondeur du livre de fourmis, alors j'ai essayé de comprendre mon niveau de compréhension en l'expliquant en détail. Veuillez signaler toute erreur.