【連結の判定】STEP: 3 有向グラフの隣接行列と隣接リスト(paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 3 有向グラフの隣接行列と隣接リスト
※リンク先へ移動する為には「paiza」へのログインが必要です。
【連結の判定】STEP1、STEP2を併せた問題です。隣接行列と隣接リストの両方を出力します。
解答例
|
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 27 28 29 30 31 32 33 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $m = $input[1]; for($i = 0;$i < $n;$i++){ for($j = 0;$j < $n;$j++){ $a_array[$i][$j] = 0; // 隣接行列の配列を作成 $b_array[$i] = array(); // 隣接リストの配列を作成 } } for($i = 0;$i < $m;$i++){ $test = explode(" ",trim(fgets(STDIN))); $a = $test[0] - 1; $b = $test[1] - 1; $a_array[$a][$b] = 1; // 隣接行列を作成 $b_array[$a][] = $b; // 隣接リストの作成 } foreach($a_array as $value1){ // 隣接行列を出力 foreach($value1 as $value2){ echo $value2; } echo "\n"; } foreach($b_array as $value1){ // 隣接リストを出力 sort($value1); foreach($value1 as $value2){ echo $value2; } echo "\n"; } ?> |
