AcWing 837. 连通块中点的数量 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-22 10:43:48
,
所有人可见
,
阅读 756
// 从1开始
let parent = [], size = [];
let find = x => {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
//a 合并到 b
let merge = (a, b) => {
let roota = find(a), rootb = find(b);
parent[roota] = rootb;
if(roota === rootb) return;
size[rootb] += size[roota];
}
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, m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
n = a[0], m = a[1];
for (let i = 0; i <= n; i++) {
parent.push(i);
size.push(1);
}
} else if (lineIdx <= m) {
switch (line[0]) {
case 'C': {
let arr = getInputNums(line.slice(1));
if (parent[arr[0]] !== parent[arr[1]])
merge(arr[0], arr[1]);
break;
}
case 'Q': {
if(line[1] === '1'){
let arr = getInputNums(line.slice(2));
console.log(find(arr[0]) === find(arr[1]) ? 'Yes' : 'No');
}
else{
let arr = getInputNums(line.slice(2));
console.log(size[find(arr[0])]);
}
break;
}
}
}
});
});