위상 정렬

 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 X) *** 

 

 

1. 진입 차수가 0인 정점을 찾아 Queue에 넣는다.

2. Queue에서 정점 하나를 뺀후, 해당 정점에 연결된 간선을 제거한다.

3. 2번을 통해 간선이 제거된 정점이 진입차수가 0이라면  Queue에 추가한다.

4. 1번으로 다시 간다.

 

V = 정점

E = 간선

시간 복잡도는 O(V+E)

 

사이클이 없는 경우

 

만약 사이클이 있는 경우는 아래 그림과 같다

N = 6 일 경우

결과 배열에 총 6개가 아닌 [1, 6] 단 2개만 들어있을 것이다.

나머지는 진입 차수가 1보다 크기 때문에다.

사이클이 있는 경우

 

아래는 배운 위상정렬로 풀 수 있는 문제이다.

2252번: 줄 세우기

const fs = require("fs");
const stdin = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `4 2
    4 2
    3 1`
).split("\n");

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [N, M] = input()
  .trim()
  .split(" ")
  .map((v) => +v);

const edgeCountList = new Array(N).fill(null).map((_) => 0);
const graph = new Array(N).fill(null).map((_) => []);
for (let i = 0; i < M; i++) {
  const [a, b] = input()
    .trim()
    .split(" ")
    .map((v) => +v);
  edgeCountList[b - 1]++;
  graph[a - 1].push(b - 1);
}

const answer = [];
const q = [];
for (let i = 0; i < N; i++) {
  if (edgeCountList[i] === 0) {
    q.push(i);
    answer.push(i + 1);
  }
}
while (q.length > 0) {
  const v = q.shift();
  for (let i of graph[v]) {
    if (--edgeCountList[i] === 0) {
      q.push(i);
      answer.push(i + 1);
    }
  }
}
console.log(...answer);