Index
問題はこちら
自分の回答は以下の通り
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
fun main(args: Array<String>) { val (N,M) = readLine()!!.split(" ").map(String::toInt) //二次元配列 var list = Array(N) { BooleanArray(N) } //辺が存在するものをtrueとする for(i in 0 until M) { //配列の要素番号にするため-1したものを取得 val (U,V) = readLine()!!.split(" ").map(String::toInt).map{ it - 1 } list[U][V] = true list[V][U] = true } var count = 0 for(i in 0 until N) { for(j in i + 1 until N) { for(k in j + 1 until N){ if(list[i][j] && list[j][k] && list[k][i]) count++ } } } println(count) } |
この問題は三角形を見つける問題と読み替えることができるので、以下の方針で三角形を見つけていく。
①Boolean型の二次元配列を使って辺の存在を表す（存在すればtrue、しなければfalse）
例えばこんな感じ。
|
1 2 |
list[0][1] = true //頂点1 - 2 を結ぶ辺が存在する list[0][2] = false//頂点1 - 3 を結ぶ辺が存在する |
②すべての辺の組み合わせを３重ループで全探索し、３辺がtrueとなる組み合わせの数を数えていけばよい。
（今回は制約を見ると全検索しても問題ないので、特に効率化を行わなくてもよい）
例えば以下の例では頂点0,1,2で結ばれた三角形が存在することになる。
|
1 |
if(list[0][1] && list[1][2] && list[2][0]) count++ |
ちなみに以下のようにもかけるらしいが、以下のコードでは短絡評価を行わないので、実行効率が悪い（今回はほぼ影響ないと思われますが）
|
1 |
if(list[0][1] and list[1][2] and list[2][0]) count++ |
