Livre en spirale en Python! Python avec un livre en spirale! (Chapitre 14 ~)

Cet article sera mis à jour de temps à autre.

Livre en spirale (Chapitre 14-)

S'il vous plaît voir ici pour le livre en spirale (~ 13 chapitres).

Chapitre 14 Structure de données avancée

Union Find Tree

class UnionFindTree():

    def __init__(self, n):
        #Nombre d'éléments dans l'arborescence entière
        self.n  = n
        #root[x]<Si 0, le nœud est la racine et sa valeur est le nombre d'éléments dans l'arborescence
        self.root = [-1] * (n+1)
        #Rang
        self.rank = [1] * (n+1)

    def find_root(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def is_same(self,x,y):
        return self.find_root(x) == self.find_root(y)

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]

J'ai importé l'arbre de recherche Union créé ci-dessus et j'ai rencontré un problème dans le livre en spirale.


from union_find_tree import UnionFindTree

n, q = map(int, input().split())

uft = UnionFindTree(n)

ans = []
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uft.unite(x,y)
    elif com == 1:
        if uft.is_same(x,y):
            ans.append(1)
        else:
            ans.append(0)
for j in ans:
    print(j)



'''
5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0
'''

Chapter15

Worshall Floyd

v, e = map(int, input().split())

inf = float("inf")

#Utiliser les bords comme dp
edges = [[inf]*v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

for w in range(v):
    edges[w][w] = 0

for k in range(v):
    for i in range(v):
        for j in range(v):
            edges[i][j] = min(edges[i][j], edges[i][k]+edges[k][j])


if any(edges[i][i] < 0 for i in range(v)):
    print("NEGATIVE CYCLE")
else:
    for x in edges:
        x = ["INF" if y == inf else str(y) for y in x]
        print(" ".join(x))

Tri topologique

[Ici](https://aotamasaki.hatenablog.com/entry/2019/12/01/%E8%9E%BA%E6%97%8B%E6%9C%AC%E3%82%92Python%E3%81 % A7% E8% A7% A3% E3% 81% 8F_Part3 # P324-DSL_2_C-Range-Search-kD-Tree) a été utilisé comme référence.

from collections import deque

v, e = map(int, input().split())
adj = [[] for _ in range( v)]
inflow = [0] * v
for _ in range(e):
    s, t = map(int, input().split())
    inflow[t] += 1
    adj[s].append(t)

def topological_sort(adj, inflow):
    is_visited = [False] * len(inflow)
    res = []

    def bfs(s):
        #À partir de s
        q = deque([s])
        is_visited[s] = True
        while q:
            p = q.popleft()
            res.append(p)
            for r in adj[p]:
                inflow[r] -= 1
                if (inflow[r] == 0) and (not is_visited[r]):
                    q.append(r)
                    is_visited[r] = True

    for x in range(len(inflow)):
        if (inflow[x] == 0) and (not is_visited[x]):
            bfs(x)
    return res

for i in topological_sort(adj, inflow):
    print(i)

Classe Cal

Il est assez facile d'implémenter la méthode Clascal (algorithme d'arborescence de surface totale minimale) en utilisant Union Find Tree.

from union_find_tree import UnionFindTree

v, e = map(int,input().split())
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append((w, s, t))

#les bords sont triés à l'avance
edges.sort()

def kuruskal(n, edges):
    uft = UnionFindTree(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uft.is_same(s, t):
            res += w
            uft.unite(s, t)
    return res

print(kuruskal(v, edges))

chapter17

Recommended Posts

Livre en spirale en Python! Python avec un livre en spirale! (Chapitre 14 ~)
Livre de fourmis avec python (Chapter3 édition intermédiaire ~)
[Python] Récupérez les fichiers dans le dossier avec Python
Créer un environnement virtuel avec conda avec Python
Travaillez dans un environnement virtuel avec Python virtualenv.
Créer une nouvelle page en confluence avec Python
Prendre une capture d'écran en Python
Comment convertir / restaurer une chaîne avec [] en python
Grattage au sélénium en Python
Créer une fonction en Python
Créer un dictionnaire en Python
Exploitez LibreOffice avec Python
Grattage avec chromedriver en python
Débogage avec pdb en Python
Jouer avec l'API d'intelligence artificielle locale de l'utilisateur en Python
Créez un Slackbot simple avec un bouton interactif en python
[Jouons avec Python] Créer un livre de comptes de ménage
Essayez d'incorporer Python dans un programme C ++ avec pybind11
Gérer les sons en Python
Grattage avec du sélénium en Python
Grattage avec Tor en Python
Tweet avec image en Python
Je veux travailler avec un robot en python.
Créer un bookmarklet en Python
Le point addictif du "raisonnement de Bayes expérimenté en Python"
Faites une loterie avec Python
Combiné avec ordinal en Python
Dessinez un cœur en Python
Exécuter un fichier Python avec une importation relative dans PyCharm
Créer un répertoire avec python
Créez un faux serveur Minecraft en Python avec Quarry
Essayez d'exécuter python dans l'environnement Django créé avec pipenv
Programme Python du "Livre qui enseigne facilement la programmation difficile"
J'ai fait un jeu de frappe simple avec tkinter de Python
Création d'un livre de lecture lié à PostgreSQL avec Flask
Créer un compte enfant de connect with Stripe en Python
Créons un script qui s'enregistre avec Ideone.com en Python.
J'ai créé une application de livre simple avec python + Flask ~ Introduction ~
Résolvez le livre en spirale (algorithme et structure de données) avec python!
J'ai fait un jeu de puzzle (comme) avec Tkinter of Python
Reconnaissance des nombres dans les images avec Python
Probablement dans un serpent Nishiki (Titre original: Peut-être en Python)
[Python] Qu'est-ce qu'une instruction with?
Ecrire une dichotomie en Python
Résoudre ABC163 A ~ C avec Python
Faites fonctionner l'imprimante de reçus avec python
Manuel de graphisme Python avec Matplotlib.
Tester avec des nombres aléatoires en Python
[python] Gérer les fonctions dans une liste
Appuyez sur une commande en Python (Windows)
GOTO en Python avec Sublime Text 3
Travailler avec LibreOffice en Python: import
100 traitements de langage avec Python
Créer un conteneur DI avec Python
Scraping avec Selenium en Python (Basic)
100 Language Processing Knock Chapitre 1 en Python
Faisons une interface graphique avec python.
Analyse CSS avec cssutils en Python
Résoudre ABC166 A ~ D avec Python
Dessinez une matrice de diagramme de dispersion avec python