AcWing 848. 有向图的拓扑序列 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2020-04-07 17:12:27
,
所有人可见
,
阅读 775
let n = 1, m = 1;
let head = new Int32Array(100010).fill(-1); //head[x] == -1 为终点
let next = new Int32Array(100010);
let val = new Int32Array(100010);
let idx = 0;
let indegree = new Int32Array(100010); //入度
let q = new Int32Array(100010); //输出序列
//头部插入,添加 a -> b 的关系
let addHead = (a, b) => {
val[idx] = b; //存放a的后续节点b
next[idx] = head[a]; //next存放当前a的第一个后续节点,在val中的位置,next[x] == -1 为不存在
head[a] = idx++; //存放新加入的a的后续节点,在val中的位置
indegree[b]++; //b的入度加1
};
let topSort = () => {
let h = 0, t = -1;
//找到入度为0的起始点
for (let i = 1; i <= n; i++) {
if (indegree[i] === 0) q[++t] = i;
}
while (h <= t) {
let tmp = q[h++];
for (let i = head[tmp]; i !== -1; i = next[i]) {
//若存在tmp的后续节点,即i !== -1,
let j = val[i];
//后续节点j的入度减1后,看是否遍历完成
if(--indegree[j] === 0) q[++t] = j;
}
}
return t == n - 1;
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
n = getInputNums(line)[0];
m = getInputNums(line)[1];
} else {
let arr = getInputNums(line);
addHead(arr[0], arr[1]);
if (lineIdx === m) {
if(topSort()){
console.log(q.slice(0, n).join(' '));
}else{
console.log('-1');
}
}
}
});
});