Essayez d'utiliser le networkx de Python avec AtCoder
Networkx disponible dans AtCoder
Avec la mise à jour du langage d'AtCoder, Python est devenu la série 3.8, mais networkx peut être utilisé. Vu le temps de traitement, je pense que les boîtiers à utiliser sont limités, mais je vais vous le présenter car je l'ai essayé.
Vous pouvez vérifier la version de chaque bibliothèque en entrant ce qui suit dans le test de code d'AtCoder. networkx contient 2.4.
import sys
print("python", sys.version)
import numpy as np
print("numpy", np.__version__)
import scipy as sp
print("scipy", sp.__version__)
import networkx as nx
print("networkx", nx.__version__)
import sklearn
print("sklearn", sklearn.__version__)
python 3.8.2 (default, Feb 26 2020, 02:56:10)
[GCC 7.4.0]
numpy 1.18.2
scipy 1.4.1
networkx 2.4
sklearn 0.22.2.post1
Essayez de résoudre le problème avec networkx
Par exemple, essayez le [Problème C] de ACL Beginner Contest (https://atcoder.jp/contests/abl/tasks/abl_c). La réponse est le nombre de composants connectés -1 car il s'agit du nombre d'arêtes nécessaires pour connecter tous les réseaux. Pour networkx, utilisez number_connected_components.
import networkx as nx
G = nx.Graph()
n, m = map(int, input().split())
G.add_nodes_from(range(n))
for i in range(m):
a, b = map(int, input().split())
G.add_edge(a-1, b-1)
print(nx.number_connected_components(G) - 1)
J'ai fait AC, mais le temps d'exécution et la mémoire sont terribles.
Cela ne semble utilisable que pour des problèmes avec une marge considérable.
Recommended Posts