Try using Python's networkx with AtCoder
Networkx available in AtCoder
With the language update of AtCoder, Python became 3.8 series, but networkx can be used. Considering the processing time, I think that the cases to use are limited, but I will introduce it because I tried it.
You can check the version of each library by entering the following in the code test of AtCoder. networkx contains 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
Try to solve the problem with networkx
For example, try C problem of ACL Beginner Contest. The answer is the number of connected components -1 because it is a matter of the number of edges required to connect all the networks. For networkx, use 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)
I did AC, but the execution time and memory are terrible.
This seems to be usable only for problems with considerable margin.
Recommended Posts