回答編集履歴
3
greedy内では経路を表示していないので表現変更
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
`circuit`は隣接行列なので、隣接リストを前提とした`dfs`にそのまま渡しても、正常に動作しません。隣接行列を前提としたコードに書き換えましょう。
|
|
5
5
|
2. **valid内で、閉路があったら 1 を、閉路が無かったら 0 を返している**
|
|
6
6
|
現状だと、`dfs`が 1 を返したら、つまり、閉路があったら 1 を返し、逆に閉路が無かったら 0 を返しています。「条件２．すべての点を回らないような閉路はつくらない」なので、0 を返すべきなのは「すべての点を回らない閉路」があった場合のみです。
|
|
7
|
-
3. **greedy内で、見つかった辺の始点を順番に並べたものを経路として
|
|
7
|
+
3. **greedy内で、見つかった辺の始点を順番に並べたものを経路として返している**
|
|
8
8
|
今回のテストデータだと、1-3, 0-3, 1-4, 0-2, 2-4の順番で辺が見つかるので、辺の始点を並べても 1->0->1->0->2 になってしまいます。0から改めて経路をたどるなどしてください。
|
|
9
9
|
|
|
10
10
|
これらの問題を修正したところ、正しい経路が表示されるようになりました。
|
2
mainのメモリ確保を見落としていたので追加
test
CHANGED
|
@@ -9,4 +9,4 @@
|
|
|
9
9
|
|
|
10
10
|
これらの問題を修正したところ、正しい経路が表示されるようになりました。
|
|
11
11
|
|
|
12
|
-
あと、経路の正しさに直接は関係ありませんが、`degree`内で`malloc`を使って確保したメモリを`free`していないのもNGです。
|
|
12
|
+
あと、経路の正しさに直接は関係ありませんが、`degree`や`main`内で`malloc`を使って確保したメモリを`free`していないのもNGです。
|
1
freeしていない問題も追加で指摘
test
CHANGED
|
@@ -8,3 +8,5 @@
|
|
|
8
8
|
今回のテストデータだと、1-3, 0-3, 1-4, 0-2, 2-4の順番で辺が見つかるので、辺の始点を並べても 1->0->1->0->2 になってしまいます。0から改めて経路をたどるなどしてください。
|
|
9
9
|
|
|
10
10
|
これらの問題を修正したところ、正しい経路が表示されるようになりました。
|
|
11
|
+
|
|
12
|
+
あと、経路の正しさに直接は関係ありませんが、`degree`内で`malloc`を使って確保したメモリを`free`していないのもNGです。
|