https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(n => Number(n));
const graph = new Array(N+1).fill(0).map(i => []);
const indegree = new Array(N+1).fill(0);
for(let i = 0 ; i < M ; i++) {
const [to, from] = input[i].split(' ').map(n => Number(n));
graph[to].push(from);
indegree[from]++;
}
const tOrder = [];
const queue = [];
for(let i = 1; i < graph.length ; i ++) {
if(indegree[i] === 0) {
queue.push(i);
break;
}
}
while(queue.length) {
const node = queue.shift();
indegree[node] = -1;
const targetNode = graph[node];
targetNode.forEach((i) => {
indegree[i]--;
});
tOrder.push(node);
for(let i = 1; i < graph.length ; i ++) {
if(indegree[i] === 0) {
queue.push(i);
break;
}
}
}
console.log(tOrder.join(" "))728x90
'Algorithm\CodingTest > Baekjoon' 카테고리의 다른 글
| [Beakjoon] [1271] 브론즈 5 - 엄청난 부자2 (0) | 2023.03.17 |
|---|---|
| [Baekjoon] [2178] DFS/BFS 실버1 - 미로 탐색 (0) | 2023.03.17 |
| [Baekjoon] [2667] DFS/BFS 실버 1 - 단지번호붙이기 (0) | 2023.03.14 |
| [ Baekjoon ] [11724] DFS/BFS 실버 2 - 연결 요소의 개수 (0) | 2023.03.14 |
| [ Baekjoon ] [1260] DFS/BFS 실버 2 - DFS와 BFS (0) | 2023.03.13 |