AtCoder で Python の networkx を使ってみる

AtCoderで利用可能なnetworkx

AtCoderの言語アップデートでPythonは3.8系になりましたが、なんとnetworkxが使えるんですね。
処理時間を考えると使うケースは限られると思いますが、試してみたのでご紹介します。

AtCoderのコードテストで下記を入れると、各ライブラリのバージョンを確認できます。
networkxは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

networkxで問題を解いてみる

例えば ACL Beginner Contest の C問題 をやってみます。
ネットワークをすべて連結するために辺を足す必要数の問題なので、連結成分の個数-1が答えです。
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)

ACしましたが、実行時間もメモリもやばいですね。
これは相当余裕のある問題でしか使えなさそうです。