弱者・凡人のための競プロ入門『競技プログラミングの鉄則』を使いこなしたい！『グラフ』編

## 記事の対象読者　鉄則本を読んでいる人へ

みなさん、競技プログラミングに励んでいますか？

いま、競技プログラミングを上達させるための一冊といえば、[競技プログラミングの鉄則](https://amzn.to/3X1XlKr)ですよね！！　

しかし、初心者の皆さん、この本を使いこなせていますか？？

わたし自身、最初はこの本の理解に時間がかかりました。

そこで、
* **ちょっと苦手意識がある**
* **得意とはいえない**

と感じているみなさんに役立てるように、鉄則本の勉強メモを記事化します！！！！

競技プログラミングに苦手意識がある人でも理解しやすいように、この記事では、以下の観点にそって鉄則本の要点を紹介します。

* 問題が伝えたい考え方
* 実装上の注意
* 習熟したい基礎

もちろん、鉄則本を読んでいる人向けの内容です。

今回扱うテーマは、**グラフ**です。

言語は、Python を使用します。

鉄則本の内容を染み込ませるために、ぜひこの記事を活用してみてください。

それでは、さっそく内容に移りましょう。


#### ほんとうの初心者さんはこちら
ちなみに、競技プログラミング初心者は、こちらの記事がおすすめです。
鉄則本の作者さんの記事です。
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】](https://qiita.com/e869120/items/f1c6f98364d1443148b3)








## A61,B61 グラフの実装方法
### この問題が伝えたい考え方
* グラフの表現方法は隣接リストを採用する。
* 入力として与えられる辺をリストのリストにする。そのリストから、隣接リストを作成する。

### 実装上の注意点
* 隣接リストの要素数はN＋1個。これは、頂点番号とインデックスを揃えるため。

### 習熟したい基礎
* リスト内包表記により、入力である辺をリストのリストにする。`edges = [ list(map(int, input().split())) for i in range(M) ]`
* 隣接リストの初期化。空リストを要素にもつリストをリスト内包表記で作成する。`G = [ list() for i in range(N + 1) ]`
* リストのリストの要素へのfor文でのアクセス方法。`for a, b in edges:`
* `friend.index(mx)` これはリスト friend の中で、値 mx が最初に現れるインデックス（位置）を探します。



## A62 深さ優先探索
### この問題が伝えたい考え方
* グラフの連結判定には、深さ優先探索が使える

### 実装上の注意点
* Pythonの場合、再起呼び出しの深さの上限を設定する必要がある。`sys.setrecursionlimit(120000)`


## B62 移動経路の記録
### この問題が伝えたい考え方
* 単純パスの求め方
* 深さ優先探索で頂点を訪れるたびに経路に追加する。ただし、それ以上先に行けな頂点は経路から削除する。

### 実装上の注意点
* それ以上深く探索することのない頂点では、DFS関数は何もしない。よって、何もせず、一つ上の階層の処理に戻る。ここで、何もしないのではなく、それ以上深く探索できない頂点を経路から削除すればいい。



### 習熟したい基礎
* `sys.exit(0)`は、Pythonプログラムを正常終了させるために使用されます。引数には終了ステータスコードを指定し、0は正常終了、0以外はエラー終了を意味します。
* sys.exitはSystemExit例外を発生させるため、必要に応じて例外処理で捕捉することができます。
* sys.exitを使うことで、プログラムの任意の場所で実行を停止させることができるため、特定の条件下での異常終了やエラー処理に役立ちます。

## A63 幅優先探索
### この問題が伝えたい考え方
* 重みなしグラフの最短距離探索には、幅優先探索が使える。
* 幅優先探索には、データ構造のキューを使う。

### 実装上の注意
* 問題の条件より、到達できない頂点への距離は-1とする。よって、初期値には、-1を設定しておくと便利。


### 習熟したい基礎
* `from collections import deque`により、キューを使う。
* `Q = deque()`キューの初期化。追加や削除は、リストの書き方と同じ。


## B63
### この問題が伝えたい考え方
* 二次元の迷路をグラフに見立てる。
* マス（i, j）の頂点番号を、`(i-1) * W(迷路の列数) + j`によって隣接リストにマッピングする。
* 隣接リストで表現できれば、あとはただの幅優先探索の問題。


## A64 ダイクストラ法
### この問題が伝えたい考え方
* 重み付き無効グラフの最短経路問題には、ダイクストラ法が使える。
* 距離の暫定値を更新する（動的計画法の配る遷移形式に近い。iが確定しているとき、i+1やi+2の値を更新する考え方）


### 実装上の注意点
* 暫定値が最小の頂点を高速に求めるために、優先度付きキューが使える。
* 訪問済みの頂点を追跡し、すでに最短距離が確定した頂点を再び処理しないようにする。
* 暫定値の初期値には、大きな数値を設定する。本書の場合、`INF = 10 ** 10`などを設定。

### 習熟したい基礎
* 優先度つきキューの使い方。`import heapq`する。
* キューへの追加。`heapq.heappush(Q, (cur[1], 1))`
* キューからの削除と取得。`pos = heapq.heappop(Q)[1]`
* 重みつきグラフの隣接リスト表現↓　。タプルで、(頂点, その頂点への重み)で表現する。

```python
for a, b, c in edges:
	G[a].append((b, c))
	G[b].append((a, c))
```

```python
G = [[], [(2, 15), (4, 20)], [(1, 15), (3, 65), (5, 4)], [(2, 65), (6, 50)], [(1, 20), (5, 30)], [(2, 4), (4, 30), (6, 8)], [(3, 50), (5, 8)]]
```



## B64 
### この問題が伝えたい考え方
* 具体的な最短経路は、動的計画法の復元と似たような考え方で求められる。

```python
goal = N
path = [goal]
now = goal

while now != 1:
    for to, w in G[now]:
        if cur[to] + w == cur[now]:
            path.append(to)
            now = to
            break

print(*path[::-1])
```



### 習熟したい基礎
* アンパック演算子 `*` は、リストやタプルの要素を個別の引数として展開します。例えば、リスト `lst = [1, 2, 3]` があるとき、`print(*lst)` は `print(1, 2, 3)` と同じ意味になります。


## A66 Union-Find木

### この問題が伝えたい考え方
* Union-Find木は、グループ分けを効率的に管理することができるデータ構造。
* グループとグループの統合、要素が同じグループにあるのかどうか、を高速に処理できる。
* Union-Find木は、**根付き木**構造になっている。


### 実装上の注意点
* 計算量を減らすために、グループを結合するとき、頂点数の多いグループを上に持っていく。



## A67 最小全域木

### この問題が伝えたい考え方
* 最小全域木　すべての頂点が繋がっていてその長さが最小のもの。
* 最小全域木は、「短い辺から追加していく」という貪欲法によって求められる。
* 実装上は、クラスカル法と呼ばれていて、配列のソートとUnion-Findを用いて実装できる。


### 実装上の注意
* Union-Findのクラスさえ用意してあれば、クラスカル法の実行部分は少ない。
* 辺の長さを小さい順にソートすることを忘れずに。

```python
# 辺を長さの小さい順にソートする
edges.sort(key = lambda x: x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
	if not uf.same(a, b):
		uf.unite(a, b)
		answer += c
```


### 習熟したい基礎
* リストのsortメソッド。
* `key引数`　sortメソッドの key引数は、並べ替えの基準となる値を返す関数を指定します。この関数はリストの各要素に適用され、その結果が並べ替えに使用されます。
* `lambda x: x[2]`　lambda は匿名関数を作成するためのキーワードです。lambda x: x[2] は、引数 x を受け取り、x の第3要素（インデックス2の要素）を返す関数を定義しています。ここで、x はリスト edges の各要素を表しています。各要素がリストやタプル (a, b, c) であれば、x[2] は c になります。


## おすすめ記事
* [論理学って何を扱うの？論理学入門](https://qiita.com/kyogoku_meta/items/7dc1c17f78bc36d11346)
* [線形代数の「背景と概念」をもっとよく分かりたい【数学弱者・凡人のための線形代数入門】](https://qiita.com/kyogoku_meta/items/077e9972dcd7b08d6473)
* [弱者・凡人のための競技プログラミング入門『競技プログラミングの鉄則』本を使いこなしたい『二分探索』編](https://qiita.com/kyogoku_meta/items/91b32773f045d0ef560b)