【連結の判定】STEP: 1 隣接行列 (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 1 隣接行列 (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
初めてこの問題に挑戦した時、「隣接行列」ってなんぞや？ってなりました(;’∀’)
実は今でもよく分かってません(;^ω^)
まあ例えば頂点が3つあるのなら、「3 × 3」の多次元配列をつくり0を保存。更に結合してる頂点同士、例えば「1」と「2」が結合しているなら「隣接行列[1][2]」、「隣接行列[2][1]」と対になる位置に「1」を保存することで結合している頂点と辺を表現していることはなんとなく分かりました。
解答例
|
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 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $m = $input[1]; for($i = 0;$i < $n;$i++){ //隣接行列の作成 for($j = 0;$j < $n;$j++){ $array[$i][$j] = 0; } } for($i = 0;$i < $m;$i++){ $test = explode(" ",trim(fgets(STDIN))); //結ばれている頂点のデータ取得 $a = $test[0] - 1; //結ばれている頂点「a」 $b = $test[1] - 1; //結ばれている頂点「b」 $array[$a][$b] = 1; //隣接行列に結ばれている頂点に「a」「b」の配列位置に「1」を保存する $array[$b][$a] = 1; //隣接行列に結ばれている頂点に「b」「a」の配列位置に「1」を保存する } foreach($array as $value){ //答えを出力する foreach($value as $item){ echo $item; } echo "\n"; } ?> |
