AcWing 240. 食物链 ( JavaScript )
原题链接
中等
作者:
gaobowen
,
2019-11-22 18:36:21
,
所有人可见
,
阅读 710
let parent = [];
let deep = new Int32Array(50010);
let falseCount = 0;
//每次查完后路径被压缩到根节点下,避免了重复计算
let find = x => {
if (parent[x] !== x) {
let t = find(parent[x]);
deep[x] += deep[parent[x]];
parent[x] = t;
}
return parent[x];
}
let same = (a, b) => {
let roota = find(a), rootb = find(b);
if (roota === rootb && (deep[a] - deep[b]) % 3) falseCount++;//同根节点,层级关系不符合, 非同类
else if (roota !== rootb) { //不同根节点合并
parent[rootb] = roota; //b 插到 a 下
//a到b的高度差 == roota到rootb的高度差,使得下次find(a)==find(b)后deep[a] == deep[b]
deep[rootb] = deep[a] - deep[b];
//第二种,a 插到 b 下
//parent[roota] = rootb;
//deep[roota] = deep[b] - deep[a];
}
}
let eat = (a, b) => {
let roota = find(a), rootb = find(b);
//‘(deep[a]-1 - deep[b]) % 3’ 相当于a自降一级与b比较,%3 == 0时,刚好符合 a 吃 b
if (roota === rootb && (deep[a] - 1 - deep[b]) % 3) falseCount++;
else if (roota !== rootb) {
// a吃b的逻辑, b插到a下,形象的表示 a在上 b在下, AC过。
parent[rootb] = roota;
deep[rootb] = deep[a] - deep[b] - 1; //b恰好少一级,符合a吃b。
//第二种, 写法与第二种same保持一致
//parent[roota] = rootb;
//deep[roota] = deep[b] - deep[a] + 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 () {
let n = 0, k = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
n = a[0], k = a[1];
for (let i = 0; i <= n; i++) {
parent.push(i);
}
} else if (lineIdx <= k) {
let arr = getInputNums(line.slice(1));
if (arr[0] > n || arr[1] > n) {
falseCount++;
if (lineIdx === k) console.log(falseCount);
return;
}
switch (line[0]) {
case '1': {
same(arr[0], arr[1])
break;
}
case '2': {
eat(arr[0], arr[1])
break;
}
}
if (lineIdx === k) console.log(falseCount);
}
});
});