0Pricing
Competitive Programming Academy · レッスン

入力から隣接リストを作る

コンテストで与えられるグラフを構築します

「入力から隣接リストを作る」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

グラフとは何か

グラフとは、ノードと呼ばれる点を、エッジと呼ばれる線で結んだものです。道路で結ばれた都市は、すでに知っているグラフの例です。🗺️

ノードとエッジ

各ノードは対象を表し、各エッジは2つのノードが接続されていることを表します。コンテストのグラフでは、通常ノードを1からnまで番号付けします。

隣接リスト

コンテストで定番の保存方法は隣接リストです。各ノードについて、直接つながっている隣接ノードのリストを保持します。

adj = [[] for _ in range(n + 1)]

行列を使わない理由

行列はnの2乗個のメモリを使うため、nが大きいと急激に増加します。隣接リストなら存在するエッジだけを保存するため、大規模なグラフにも対応できます。

最初の行を読む

ほとんどの入力は、最初に2つの数値を持ちます。nがノード数、mがエッジ数です。最初に読み取って、いくつのエッジを読むのか把握しましょう。

n, m = map(int, input().split())

1行に1つのエッジ

続くm行には、それぞれu vという組が指定されます。この1つのエッジは、uとvが直接接続されていることを表します。

u, v = map(int, input().split())

無向グラフは双方向

無向エッジでは、接続を両方向に追加します。uからvへも、vからuへも移動できます。

adj[u].append(v)
adj[v].append(u)

有向グラフは一方向

有向エッジでは、uからvへの接続だけを保存します。どちらの種類かを、問題文で注意深く確認してください。

adj[u].append(v)

ループで構築する

m回ループし、各組を読み取ってリストに追加します。ループが終わると、隣接リストにグラフ全体が格納されています。

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

1始まりと0始まり

ノード番号が1から始まる場合は、インデックスnを有効にするため、リストのサイズをn+1にします。インデックス付けを取り違えると、気づきにくいバグの原因になります。

ノードの隣接ノードを訪れる

構築後の探索は簡単です。あるノードのadjをループすれば、すべての隣接ノードに1ステップで到達できます。

for nb in adj[u]:
    print(nb)

確認問題

無向エッジu vを読み取りました。何を保存しますか。

復習

隣接リストとしてグラフを構築できるようになりました。nとmを読み、エッジをループし、無向グラフなら両方向に追加します。🎉

よくある質問

「入力から隣接リストを作る」レッスンは無料ですか？

はい。「入力から隣接リストを作る」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「入力から隣接リストを作る」で何を学びますか？

コンテストで与えられるグラフを構築します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「入力から隣接リストを作る」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 入力から隣接リストを作る
  2. 重みなし最短経路のための BFS
  3. DFS、再帰、反復スタック
  4. 連結成分と Flood Fill
← Competitive Programming Academyに戻る