Versuchen Sie, Pythons networkx mit AtCoder zu verwenden
Networkx in AtCoder verfügbar
Mit dem Sprachupdate von AtCoder wurde Python zur 3.8-Serie, aber networkx kann verwendet werden. In Anbetracht der Verarbeitungszeit denke ich, dass die zu verwendenden Fälle begrenzt sind, aber ich werde es einführen, weil ich es versucht habe.
Sie können die Version jeder Bibliothek überprüfen, indem Sie im Codetest von AtCoder Folgendes eingeben. networkx enthält 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
Versuchen Sie, das Problem mit networkx zu lösen
Versuchen Sie beispielsweise C-Problem des ACL-Anfängerwettbewerbs. Die Antwort ist die Anzahl der verbundenen Komponenten -1, da es sich um die Anzahl der Kanten handelt, die zum Verbinden aller Netzwerke erforderlich sind. Verwenden Sie für networkx 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)
Ich habe AC gemacht, aber die Ausführungszeit und der Speicher sind schrecklich.
Dies scheint nur für Probleme mit beträchtlichem Spielraum verwendbar zu sein.
Recommended Posts