[アルゴリズムベース]位相位置合わせ

先決問題
ex)「4科目を履修するためには、1科目を履修しなければなりません.」

受講の順番は?

アクセス方法

ノードごとに1度を計算します.

のステップ0からQに進む.

0のノードが持つルートのレベルを減算します.
(負の場合、次数が0の場合はqueue)

queueのlengthがあるまで繰り返す.
n:ノード総数
m:入力した幹線数
Node:接続された情報
-✔｣完全コード

function solution(n, m, node) {

  let answer = [];
  let graph = Array.from(Array(n + 1), () => Array().fill(0));
  let indegrees = Array(n + 1).fill(0);

  let queue = [];

  for (let [a, b] of node) {
    graph[a].push(b);
    indegrees[b]++;
  }


  // 0인 애들을 첫 스타드 애들로 써야하니까 0 있는 애들은 queue 에 세팅한다 
  for (let i = 1; i < n + 1; i++) {
    if (indegrees[i] === 0) queue.push(i);
  }

  while (queue.length) {

    let check = queue.shift();
    answer.push(check);


    for (let next of graph[check]) {
      indegrees[next]--;
      if (indegrees[next] === 0) queue.push(next);
    }


  }

  return answer;
}

位相位置合わせの問題

Problem | 列に並ぶ

const inputs = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .split("\n");

let [n, m] = inputs[0].split(" ").map(Number);
let graph = Array.from(Array(n + 1), () => Array());
let indegree = new Array(n + 1).fill(0);

for (let i = 0; i < m; i++) {
  let [x, y] = inputs[i + 1].split(" ").map(Number);
  graph[x].push(y);
  indegree[y]++;
  // 그래프 초기화
}

let queue = [];
let answer = [];
for (let i = 1; i <= n; i++) {
  if (indegree[i] === 0) queue.push(i);
}

while (queue.length) {
  let nx = queue.shift();
  answer.push(nx);
  for (let next of graph[nx]) {
    indegree[next]--;
    if (indegree[next] === 0) queue.push(next);
  }
}

console.log(answer.join(" "));