回答編集履歴
12
表内の数字が行番号だとわからないので追記
test
CHANGED
|
@@ -27,7 +27,7 @@
|
|
|
27
27
|
|
|
28
28
|
以下のように一対一に対応することが分かります。
|
|
29
29
|
|
|
30
|
-
|引用コード|ご提示のコード|説明(カッコ内はご提示のコード)|
|
|
30
|
+
|引用コード行|ご提示のコード行|説明(カッコ内はご提示のコード)|
|
|
31
31
|
|:--:|:--:|--|
|
|
32
32
|
|1-3|36-42|初期ノードのdist(level)を0にしてキューに登録|
|
|
33
33
|
|6|44|キューが空になるまで探索を行う|
|
11
幅優先探索を理解しているか確認
test
CHANGED
|
@@ -1,3 +1,52 @@
|
|
|
1
|
+
まず確認したいのは、幅優先探索を本当に理解しているか、ということです。
|
|
2
|
+
幅優先探索が理解できていれば「この問題のプログラムの34行目から始まる深さ優先探索のやっていることの見当がつかず」という事態にはなりません。
|
|
3
|
+
なぜなら、ご提示のコードは、一般的な幅優先探索のコードとほぼ一対一に対応するからです。
|
|
4
|
+
|
|
5
|
+
こちらの記事「[BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜](https://qiita.com/drken/items/996d80bcae64649a6580)」から、「BFSの実装テンプレ」の実処理部分を引用させていただいて、比較してみましょう。
|
|
6
|
+
|
|
7
|
+
```c++
|
|
8
|
+
// 初期条件 (頂点 0 を初期ノードとする)
|
|
9
|
+
dist[0] = 0;
|
|
10
|
+
que.push(0); // 0 を橙色頂点にする
|
|
11
|
+
|
|
12
|
+
// BFS 開始 (キューが空になるまで探索を行う)
|
|
13
|
+
while (!que.empty()) {
|
|
14
|
+
int v = que.front(); // キューから先頭頂点を取り出す
|
|
15
|
+
que.pop();
|
|
16
|
+
|
|
17
|
+
// v から辿れる頂点をすべて調べる
|
|
18
|
+
for (int nv : G[v]) {
|
|
19
|
+
if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない
|
|
20
|
+
|
|
21
|
+
// 新たな白色頂点 nv について距離情報を更新してキューに追加する
|
|
22
|
+
dist[nv] = dist[v] + 1;
|
|
23
|
+
que.push(nv);
|
|
24
|
+
}
|
|
25
|
+
}
|
|
26
|
+
```
|
|
27
|
+
|
|
28
|
+
以下のように一対一に対応することが分かります。
|
|
29
|
+
|
|
30
|
+
|引用コード|ご提示のコード|説明(カッコ内はご提示のコード)|
|
|
31
|
+
|:--:|:--:|--|
|
|
32
|
+
|1-3|36-42|初期ノードのdist(level)を0にしてキューに登録|
|
|
33
|
+
|6|44|キューが空になるまで探索を行う|
|
|
34
|
+
|7-8|45-46|キューから先頭頂点を取り出す|
|
|
35
|
+
|11|47-49|v(left) から辿れる頂点をすべて調べる|
|
|
36
|
+
|12|50|すでに発見済みの頂点は探索しない|
|
|
37
|
+
|14-16|51-52|新たな白色頂点 nv(next) について距離情報を更新してキューに追加する|
|
|
38
|
+
|
|
39
|
+
差分は以下項目のみとなります。
|
|
40
|
+
|
|
41
|
+
- 初期ノードが複数ある
|
|
42
|
+
- 辿れる頂点の計算方法が異なる(引用コードは`G`から、ご提示のコードは`list`と`matching`から)
|
|
43
|
+
|
|
44
|
+
つまり、幅優先探索が理解できていれば、上記2点を直接質問するはずなのです。
|
|
45
|
+
|
|
46
|
+
もし幅優先探索が理解できていないのであれば、まずは上で引用したページの説明を読んで理解してから先に進むことをお勧めします。
|
|
47
|
+
|
|
48
|
+
---
|
|
49
|
+
|
|
1
50
|
基本的な考え方は、こちらで説明されているので、まずはこちらを読んで理解してください。
|
|
2
51
|
|
|
3
52
|
[二部グラフの最大マッチングと増加道](https://manabitimes.jp/math/1147)
|
10
説明追加
test
CHANGED
|
@@ -14,6 +14,8 @@
|
|
|
14
14
|
|
|
15
15
|
ただし、マッチング外の辺をたどって「右」の頂点に行った後、マッチング内の辺が無くて「左」の頂点に戻れない場合は、特殊な頂点(`sizeL`)に到達するものとみなす。(75行)
|
|
16
16
|
特殊な頂点(`sizeL`)への最短移動距離については、最大の値`sizeL`をあらかじめ入れておく。こちらは`hodfs()`で使用する。(43行)
|
|
17
|
+
|
|
18
|
+
最終的に特殊な頂点(`sizeL`)に到達するルートが、最初に説明した「増加道」になっているというのが、このコードのポイントである。
|
|
17
19
|
|
|
18
20
|
### `hodfs()`
|
|
19
21
|
「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(`level`が増える方向なら移動可(※))を繰り返して深さ優先探索する。(64行)
|
9
文言変更
test
CHANGED
|
@@ -2,9 +2,9 @@
|
|
|
2
2
|
|
|
3
3
|
[二部グラフの最大マッチングと増加道](https://manabitimes.jp/math/1147)
|
|
4
4
|
|
|
5
|
-
Hopcroft-Karp algorithm は、こちらの方法の変種です。ものすごくざっくり説明すると、頂点が被らないよう
|
|
5
|
+
Hopcroft-Karp algorithm は、こちらの方法の変種です。ものすごくざっくり説明すると、最短の増加道を、頂点が被らないように複数同時に選んで反転することで、反転回数を減らそうというものです。
|
|
6
6
|
|
|
7
|
-
まず、最短の増加道(
|
|
7
|
+
まず、最短の増加道(頂点が被るのを許す)をすべて求めるために`hobfs()`で幅優先探索し、その中から頂点が被らないものを選んで反転するために`hodfs()`で深さ優先探索を行う、という流れになります。
|
|
8
8
|
|
|
9
9
|
### `hobfs()`
|
|
10
10
|
現在のマッチングに使われていない「左」の頂点から開始する。(35-42行)
|
8
文言変更
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
[二部グラフの最大マッチングと増加道](https://manabitimes.jp/math/1147)
|
|
4
4
|
|
|
5
|
-
Hopcroft-Karp algorithm は、こちらの
|
|
5
|
+
Hopcroft-Karp algorithm は、こちらの方法の変種です。ものすごくざっくり説明すると、頂点が被らないような最短の増加道を複数同時に見つけて反転することで、反転回数を減らそうというものです。
|
|
6
6
|
|
|
7
7
|
まず、最短の増加道(複数、頂点が被るのを許す)を求めるために`hobfs()`で幅優先探索し、その中から頂点が被らないものを選んで反転するために`hodfs()`で深さ優先探索を行う、という流れになります。
|
|
8
8
|
|
7
導入部分をもう少し詳細に
test
CHANGED
|
@@ -1,5 +1,10 @@
|
|
|
1
|
-
|
|
1
|
+
基本的な考え方は、こちらで説明されているので、まずはこちらを読んで理解してください。
|
|
2
|
+
|
|
2
|
-
|
|
3
|
+
[二部グラフの最大マッチングと増加道](https://manabitimes.jp/math/1147)
|
|
4
|
+
|
|
5
|
+
Hopcroft-Karp algorithm は、こちらの処理の変種です。ものすごくざっくり説明すると、頂点が被らないような最短の増加道を複数同時に見つけて反転することで、反転回数を減らそうというものです。
|
|
6
|
+
|
|
7
|
+
まず、最短の増加道(複数、頂点が被るのを許す)を求めるために`hobfs()`で幅優先探索し、その中から頂点が被らないものを選んで反転するために`hodfs()`で深さ優先探索を行う、という流れになります。
|
|
3
8
|
|
|
4
9
|
### `hobfs()`
|
|
5
10
|
現在のマッチングに使われていない「左」の頂点から開始する。(35-42行)
|
6
注釈を加えた位置を明示
test
CHANGED
|
@@ -3,20 +3,21 @@
|
|
|
3
3
|
|
|
4
4
|
### `hobfs()`
|
|
5
5
|
現在のマッチングに使われていない「左」の頂点から開始する。(35-42行)
|
|
6
|
-
マッチング外の辺→マッチング内の辺の順番でたどって「左」の頂点に戻る移動を1セットとしたとき、ある「左」の頂点にたどり着くまでに最短で何セットの移動が必要か(`level`のこと)を幅優先探索で求める。(44-55行)
|
|
6
|
+
マッチング外の辺→マッチング内の辺の順番でたどって「左」の頂点に戻る移動(※)を1セットとしたとき、ある「左」の頂点にたどり着くまでに最短で何セットの移動が必要か(`level`のこと)を幅優先探索で求める。(44-55行)
|
|
7
|
+
|
|
8
|
+
(※) 実際には、「マッチング外の辺→マッチング内の辺」ではなく「すべての辺→マッチング内の辺」の移動をしている。しかし、「マッチング内の辺→マッチング内の辺」とたどると元の頂点(処理済み)に戻るため、実質「マッチング外の辺→マッチング内の辺」しか処理されない。
|
|
7
9
|
|
|
8
10
|
ただし、マッチング外の辺をたどって「右」の頂点に行った後、マッチング内の辺が無くて「左」の頂点に戻れない場合は、特殊な頂点(`sizeL`)に到達するものとみなす。(75行)
|
|
9
11
|
特殊な頂点(`sizeL`)への最短移動距離については、最大の値`sizeL`をあらかじめ入れておく。こちらは`hodfs()`で使用する。(43行)
|
|
10
12
|
|
|
13
|
+
### `hodfs()`
|
|
11
|
-
|
|
14
|
+
「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(`level`が増える方向なら移動可(※))を繰り返して深さ優先探索する。(64行)
|
|
12
15
|
|
|
13
|
-
### `hodfs()`
|
|
14
|
-
|
|
16
|
+
(※)「`level`が増える方向なら移動可」という判定にしているため、特殊な頂点(`sizeL`)への移動は常に成功する。
|
|
17
|
+
|
|
15
18
|
最後に特殊な頂点(`sizeL`)に到達できるか判定する。(58行)
|
|
16
19
|
ただし、すでに探索済みの頂点は除く。(59-60行)
|
|
17
20
|
到達できたら、移動経路上の辺のマッチング内/外をすべて反転して`true`を返す。(65-66行)
|
|
18
|
-
|
|
19
|
-
※「`level`が増える方向なら移動可」という判定にしているため、特殊な頂点(`sizeL`)への移動は常に成功する。
|
|
20
21
|
|
|
21
22
|
### `solve()`
|
|
22
23
|
`hobfs()`で`level`を求める。(78行)
|
5
特殊な頂点の説明追加、すべての辺→マッチング内の辺を探索している件の説明追加
test
CHANGED
|
@@ -6,12 +6,17 @@
|
|
|
6
6
|
マッチング外の辺→マッチング内の辺の順番でたどって「左」の頂点に戻る移動を1セットとしたとき、ある「左」の頂点にたどり着くまでに最短で何セットの移動が必要か(`level`のこと)を幅優先探索で求める。(44-55行)
|
|
7
7
|
|
|
8
8
|
ただし、マッチング外の辺をたどって「右」の頂点に行った後、マッチング内の辺が無くて「左」の頂点に戻れない場合は、特殊な頂点(`sizeL`)に到達するものとみなす。(75行)
|
|
9
|
+
特殊な頂点(`sizeL`)への最短移動距離については、最大の値`sizeL`をあらかじめ入れておく。こちらは`hodfs()`で使用する。(43行)
|
|
10
|
+
|
|
11
|
+
※実際には、「マッチング外の辺→マッチング内の辺」ではなく「すべての辺→マッチング内の辺」で探索している。しかし、「マッチング内の辺→マッチング内の辺」とたどると元の頂点(処理済み)に戻るため、実質「マッチング外の辺→マッチング内の辺」しか処理されない。
|
|
9
12
|
|
|
10
13
|
### `hodfs()`
|
|
11
14
|
「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(`level`が増える方向なら移動可)を繰り返して深さ優先探索する。(64行)
|
|
12
15
|
最後に特殊な頂点(`sizeL`)に到達できるか判定する。(58行)
|
|
13
16
|
ただし、すでに探索済みの頂点は除く。(59-60行)
|
|
14
17
|
到達できたら、移動経路上の辺のマッチング内/外をすべて反転して`true`を返す。(65-66行)
|
|
18
|
+
|
|
19
|
+
※「`level`が増える方向なら移動可」という判定にしているため、特殊な頂点(`sizeL`)への移動は常に成功する。
|
|
15
20
|
|
|
16
21
|
### `solve()`
|
|
17
22
|
`hobfs()`で`level`を求める。(78行)
|
4
念のため、sizeLとsizeRの説明に+1追加
test
CHANGED
|
@@ -22,8 +22,8 @@
|
|
|
22
22
|
|
|
23
23
|
|メンバ変数名|説明|
|
|
24
24
|
|---|---|
|
|
25
|
-
|`sizeL`|「左」の頂点の番号の最大値|
|
|
25
|
+
|`sizeL`|「左」の頂点の番号の最大値+1|
|
|
26
|
-
|`sizeR`|「右」の頂点の番号の最大値|
|
|
26
|
+
|`sizeR`|「右」の頂点の番号の最大値+1|
|
|
27
27
|
|`list`|「左」の頂点から辺をたどって到達できる「右」の頂点(複数)|
|
|
28
28
|
|`seen`|`hodfs()`で「左」の頂点が探索済みかの判定に使う|
|
|
29
29
|
|`matched`|「左」の頂点がマッチングに含まれるか|
|
3
深さ優先探索と明示
test
CHANGED
|
@@ -8,7 +8,7 @@
|
|
|
8
8
|
ただし、マッチング外の辺をたどって「右」の頂点に行った後、マッチング内の辺が無くて「左」の頂点に戻れない場合は、特殊な頂点(`sizeL`)に到達するものとみなす。(75行)
|
|
9
9
|
|
|
10
10
|
### `hodfs()`
|
|
11
|
-
「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(`level`が増える方向なら移動可)を
|
|
11
|
+
「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(`level`が増える方向なら移動可)を繰り返して深さ優先探索する。(64行)
|
|
12
12
|
最後に特殊な頂点(`sizeL`)に到達できるか判定する。(58行)
|
|
13
13
|
ただし、すでに探索済みの頂点は除く。(59-60行)
|
|
14
14
|
到達できたら、移動経路上の辺のマッチング内/外をすべて反転して`true`を返す。(65-66行)
|
2
sizeL,sizeRも抜けてた
test
CHANGED
|
@@ -22,6 +22,8 @@
|
|
|
22
22
|
|
|
23
23
|
|メンバ変数名|説明|
|
|
24
24
|
|---|---|
|
|
25
|
+
|`sizeL`|「左」の頂点の番号の最大値|
|
|
26
|
+
|`sizeR`|「右」の頂点の番号の最大値|
|
|
25
27
|
|`list`|「左」の頂点から辺をたどって到達できる「右」の頂点(複数)|
|
|
26
28
|
|`seen`|`hodfs()`で「左」の頂点が探索済みかの判定に使う|
|
|
27
29
|
|`matched`|「左」の頂点がマッチングに含まれるか|
|
1
listの説明が抜けていた
test
CHANGED
|
@@ -22,6 +22,7 @@
|
|
|
22
22
|
|
|
23
23
|
|メンバ変数名|説明|
|
|
24
24
|
|---|---|
|
|
25
|
+
|`list`|「左」の頂点から辺をたどって到達できる「右」の頂点(複数)|
|
|
25
26
|
|`seen`|`hodfs()`で「左」の頂点が探索済みかの判定に使う|
|
|
26
27
|
|`matched`|「左」の頂点がマッチングに含まれるか|
|
|
27
28
|
|`level`|「左」の頂点にたどり着くまでに何セットの移動が必要か|
|