回答編集履歴
1
具体例追記
test
CHANGED
|
@@ -13,3 +13,79 @@
|
|
|
13
13
|
そして、`G[cur]`は、`cur`につながる辺の`vector`になります。
|
|
14
14
|
|
|
15
15
|
辺の`vector`について、頂点のインデックス番目の要素を取得しているのが誤りです。
|
|
16
|
+
|
|
17
|
+
|
|
18
|
+
|
|
19
|
+
---
|
|
20
|
+
|
|
21
|
+
具体的に、サンプル1で何が起こっているかを順に追っていきましょう。
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
まず、入力の読み込みで、A,Gはそれぞれ以下のようになります。
|
|
26
|
+
|
|
27
|
+
({}はvector、()はpairのつもりです)
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
A = { 1, 2, 1, 0, 3 };
|
|
32
|
+
|
|
33
|
+
G = { { (1,0) }, { (0,0), (2,1) }, { (1,1), (3,2) }, { (2,2) } };
|
|
34
|
+
|
|
35
|
+
|
|
36
|
+
|
|
37
|
+
読み込んだ後のforループで、i = 1 の場合の処理を追ってみましょう。
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
まず、
|
|
42
|
+
|
|
43
|
+
```c++
|
|
44
|
+
|
|
45
|
+
prev_v.assign(N, INF);
|
|
46
|
+
|
|
47
|
+
prev_v[A[i]] = -1;
|
|
48
|
+
|
|
49
|
+
dfs(A[i], A[i + 1]);
|
|
50
|
+
|
|
51
|
+
```
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
|
|
55
|
+
により、prev_vは以下のようになります。
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
prev_v = { INF, 2, -1, 2 };
|
|
60
|
+
|
|
61
|
+
|
|
62
|
+
|
|
63
|
+
次に、
|
|
64
|
+
|
|
65
|
+
```c++
|
|
66
|
+
|
|
67
|
+
int cur = A[i + 1];
|
|
68
|
+
|
|
69
|
+
```
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
により、cur = 1 となります。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
その次の`while`の条件は当然満たすとして、問題の以下の処理について考えます。
|
|
78
|
+
|
|
79
|
+
```c++
|
|
80
|
+
|
|
81
|
+
int edge_id = G[cur][prev_v[cur]].second;
|
|
82
|
+
|
|
83
|
+
```
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
G[cur] = { (0,0), (2,1) }、prev_v[cur] = 2 なので、
|
|
88
|
+
|
|
89
|
+
G[cur][prev_v[cur]] は、{ (0,0), (2,1) } の2番目の要素を取得しようとします。
|
|
90
|
+
|
|
91
|
+
しかし、要素が2つしかないので範囲外アクセスとなります。
|