【連結の判定】STEP: 2 隣接リスト (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 2 隣接リスト (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
今回は結合している頂点の番号のみを出力します。「行列リスト」というみたいですね(‘ω’)
例えば「頂点1が、頂点2と頂点3と結合している」場合、1行目に「12」を出力、「頂点2が頂点1と頂点3と結合している」場合、2行目に「02」を出力といった感じです。
最初問題の意味を捉えるのに苦労しましたが、意味が分かると簡単な問題です。
色々な再現方法はあるので自分のやり易い方法で正解を導くのが、この問題の場合はいいかも(;’∀’)
解答例
|
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++){ $array[] = array(); //頂点の数だけn次の多次元配列を作る } for($i = 0;$i < $m;$i++){ $test = explode(" ",trim(fgets(STDIN))); //結合している頂点の情報を取得 $a =$test[0] - 1; //結合している頂点のナンバー - 1 $b =$test[1] - 1; //結合している頂点のナンバー - 1 $array[$a][] = $b; //多次元配列に保存する $array[$b][] = $a; //多次元配列に保存する } foreach($array as $value1){ //答えを出力する sort($value1); //配列を昇順に並べ替える foreach($value1 as $value2){ echo $value2; } echo "\n"; } ?> |
