[JS] SCC

1.条件

2.コサリ柱アルゴリズム

2.1. 隣接リストの作成

/**
 * @param {number} v 노드 갯수 
 * @param {[number, number][]} edges
 */
function makeConnection(v, edges) {
  const con = Array.from({ length: v }, () => []); // 순방향 그래프
  const recon = Array.from({ length: v }, () => []); // 역방향 그래프

  edges.forEach(([org, dest]) => {
    con[org].push(dest);
    recon[dest].push(org);
  });

  return [con, recon];
}

2.2. バックサイクルスタックの作成

/**
 * @param {number} node 
 * @param {number[]} stack
 * @param {number[][]} con
 * @param {boolean[]} visit
 */
function dfs(node, stack, con, visit) {
  con[node].forEach((next) => {
    if (visit[next]) return;
    visit[next] = true;
    dfs(next, stack, con, visit);
  });

  stack.push(node);
}

/**
 * @param {number} v 노드 갯수 
 * @param {number[][]} con
 */
function makeStack(v, con) {
  const visit = Array(v).fill(false);
  const stack = [];

  for (let node = 0; node < v; node += 1) {
    if (visit[node]) continue;
    visit[node] = true;
    dfs(node, stack, con, visit);
  }

  return stack;
}

2.3. SCC

/**
 * @param {number} v
 * @param {number[]} stack
 * @param {number[][]} recon
 */
function makeSCC(v, stack, recon) {
  const visit = Array(v).fill(false);
  const res = [];

  for (let i = stack.length - 1; i >= 0; i -= 1) {
    const node = stack[i];
    if (visit[node]) continue;

    const group = [];
    visit[node] = true;
    dfs(node, group, recon, visit);

    res.push(group);
  }

  return res;
}

2.4. 完全なコード

const [con, recon] = makeConnection(v, edges);
const stack = makeStack(v, con);
const scc = makeSCC(v, stack, recon);