ABC 061 B - Counting Roads

AtCoder JavaScript

備忘録

問題

atcoder.jp

回答

"use strict"
function Main(input) {
  input = input.trim().split('\n');
  const N = input[0].trim().split(' ').map(Number)[0];
  const M = input[0].trim().split(' ').map(Number)[1];
  const AB = input.slice(-M);
  const T = Array(N).fill(0);

  for(let i=0; i<M; i++){
    let A = AB[i].trim().split(' ').map(Number)[0];
    let B = AB[i].trim().split(' ').map(Number)[1];
    T[A-1] = T[A-1] + 1;
    T[B-1] = T[B-1] + 1;
  }
  console.log(T.join('\n'));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

N個の都市とM本の道路があり、
i(1≦i≦M)の道路は２つの都市を双方向に結んでいる。
つまり、道路と繋がっている都市をすべてカウントすることで、都市から伸びている道路の本数を得られる。