回答編集履歴
1
追記
test
CHANGED
|
@@ -1,3 +1,29 @@
|
|
|
1
1
|
線の数は、三角形の数×3 - 二つの三角形に共有されている辺の数 で出ます。
|
|
2
2
|
|
|
3
3
|
共有されてる辺の数はハッシュで管理すれば辺の数に比例する計算量で数えられます。
|
|
4
|
+
|
|
5
|
+
|
|
6
|
+
|
|
7
|
+
---
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
ハッシュで辺を管理する場合の頂点が入れ替わっただけの辺について
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
一つは正規化をするという方法
|
|
16
|
+
|
|
17
|
+
つまり、(i, j)という辺があったとき i > j ならiとjを入れ替えるというような操作を加えて順番による影響がないようにできます。
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
もう一つは今回の問題限定で、E行列において頂点は反時計回りに現れるので同じ辺が2度現れるなら、必ず頂点の順番は逆になります。なので、そのコードでいうとAに逆順で辺を入れると以前に現れた同じ辺だけカウントできます。
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
あとはぶっちゃけ想定解が何かという話になってくるので、ハッシュってなんだ?って状態なのであれば、おそらく違う方法を使うべきなんだと思います。
|
|
28
|
+
|
|
29
|
+
例えば連結成分の数が1であることがわかってるだとか、DFSやBFSについて勉強してるという前提であれば、頂点数+三角形の数-連結成分の数 で求めることが想定されてるのかもしれません。
|