徒然weed

アウトプットの場

ゆる~くpythonの練習「隣接行列編」

f:id:shintaro-football7:20191022195746p:plain

 

大学院で機械学習を主に学ぶ予定の弊ブログ管理人ですがアルゴリズム・データ構造にも興味があり、なおかつpythonの練習もしたいということで↓の本を使って、模範解答にあるC/C++ソースコードアルゴリズムを勉強しながら自分でpythonのコードを書こうという企画です。果たしてつづくのか。

なぜか第12章「グラフ」からスタートします。
今回は1問目"Graph"。最初は初級編。
最初の行に頂点数nが与えられて、続くn行に"u k v1 v2 ...vk"が与えられる。uは頂点番号、kはuの出次数、v1~vkはuに隣接する頂点の番号。そこから隣接リスト表現を出力するだけ。
詳しくは
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A

以下、書いてみたコード。

n = int(input())
a=[[0 for i in range(n)] for j in range(n)]

for i in range(n):
   info = [int(x) for x in input().split()]
   for j in info[2:]:
       a[i][j-1]=1

for v in a:
    print(*v)

#入力はこんな感じ
#4
#1 2 2 4
#2 1 4
#3 0
#4 1 3

# 解答はこんな感じ
# 0 1 0 1 
# 0 0 0 1 
# 0 0 0 0 
# 0 0 1 0 

pythonにはリスト内包があります。使ってみた。

本日のおまけ
自分が東大で学んだこともこれと似てる。