头像

gaobowen


访客:6218

离线:1个月前



gaobowen
2个月前
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');
                }
            }
        }
    });
});



gaobowen
2个月前
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');
                }
            }
        }
    });
});


活动打卡代码 AcWing 847. 图中点的层次

gaobowen
6个月前
let val = new Int32Array(200010);
let idx = 0;
let next = new Int32Array(200010);
let head = new Int32Array(100010).fill(-1);

let add = (a, b) => {
    val[idx] = b;
    next[idx] = head[a];
    head[a] = idx++;
}

let used = new Int32Array(100010);
let bfs = (x, y) => {
    let queue = [x];
    let step = -1;
    while (queue.length > 0) {
        step++;
        let nextStep = [];
        for (let i = 0; i < queue.length; i++) {
            used[queue[i]] = 1;
            if(queue[i] === y) return step;
            for (let j = head[queue[i]]; j != -1; j = next[j]) {
               if (!used[val[j]]) nextStep.push(val[j]);
            }
        }
        queue = nextStep;
    }
    return -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, m = 0;
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            m = getInputNums(line)[1];
        } else {
            let arr = getInputNums(line);
            add(arr[0], arr[1]);
            if (lineIdx === m) {
                console.log(bfs(1, n));
            }
        }
    });
});




gaobowen
6个月前
let val = new Int32Array(200010);
let idx = 0;
let next = new Int32Array(200010);
let head = new Int32Array(100010).fill(-1);

let add = (a, b) => {
    val[idx] = b;
    next[idx] = head[a];
    head[a] = idx++;
}

let used = new Int32Array(100010);
let bfs = (x, y) => {
    let queue = [x];
    let step = -1;
    while (queue.length > 0) {
        step++;
        let nextStep = [];
        for (let i = 0; i < queue.length; i++) {
            used[queue[i]] = 1;
            if(queue[i] === y) return step;
            for (let j = head[queue[i]]; j != -1; j = next[j]) {
               if (!used[val[j]]) nextStep.push(val[j]);
            }
        }
        queue = nextStep;
    }
    return -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, m = 0;
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            m = getInputNums(line)[1];
        } else {
            let arr = getInputNums(line);
            add(arr[0], arr[1]);
            if (lineIdx === m) {
                console.log(bfs(1, n));
            }
        }
    });
});



活动打卡代码 AcWing 846. 树的重心

gaobowen
6个月前

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中节点个数的最大值最小,那么这个节点被称为树的重心。

let val = new Int32Array(200010);
let idx = 0;
let next = new Int32Array(200010);//无向图需要2倍的空间存储关系
let head = new Int32Array(100010).fill(-1);

let add = (a, b) => {
    val[idx] = b;
    next[idx] = head[a];//head[a]表示旧的头结点位置
    head[a] = idx++;//新头结点
}


let n = 0, min = 100010;
let used = new Int32Array(100010);
let dfs = (x) => {
    used[x] = 1;
    let deep = 0, maxCount = 0;
    for (let i = head[x]; i !== -1; i = next[i]) {
        let node = val[i];
        if (used[node]) continue;
        let sub = dfs(node);
        maxCount = Math.max(maxCount, sub);//获取子连通块的最大点数
        deep += sub;
    }
    //计算比较剩余连通块的点数,多减1是为了减去自身节点
    maxCount = Math.max(maxCount, n - deep - 1);
    min = Math.min(min, maxCount);
    //used[x] = 0; //不能恢复会造成死循环
    return deep + 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];
        } else {
            let arr = getInputNums(line);
            add(arr[0], arr[1]);
            add(arr[1], arr[0]);
            if (lineIdx === n - 1) {
                dfs(1);
                console.log(min);
            }
        }
    });
});



gaobowen
6个月前

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中节点个数的最大值最小,那么这个节点被称为树的重心。

let val = new Int32Array(200010);
let idx = 0;
let next = new Int32Array(200010);//无向图需要2倍的空间存储关系
let head = new Int32Array(100010).fill(-1);

let add = (a, b) => {
    val[idx] = b;
    next[idx] = head[a];//head[a]表示旧的头结点位置
    head[a] = idx++;//新头结点
}


let n = 0, min = 100010;
let used = new Int32Array(100010);
let dfs = (x) => {
    used[x] = 1;
    let deep = 0, maxCount = 0;
    for (let i = head[x]; i !== -1; i = next[i]) {
        let node = val[i];
        if (used[node]) continue;
        let sub = dfs(node);
        maxCount = Math.max(maxCount, sub);//获取子连通块的最大点数
        deep += sub;
    }
    //计算比较剩余连通块的点数,多减1是为了减去自身节点
    maxCount = Math.max(maxCount, n - deep - 1);
    min = Math.min(min, maxCount);
    //used[x] = 0; //不能恢复会造成死循环
    return deep + 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];
        } else {
            let arr = getInputNums(line);
            add(arr[0], arr[1]);
            add(arr[1], arr[0]);
            if (lineIdx === n - 1) {
                dfs(1);
                console.log(min);
            }
        }
    });
});


活动打卡代码 AcWing 845. 八数码

gaobowen
6个月前

思路:广度搜索+去除重复步骤

//存放走过了的方案
let dic = new Set();
const target = '12345678x';

let left = x => x % 3 ? x - 1 : null;
let top = x => x >= 3 ? x - 3 : null;
let right = x => x % 3 < 2 ? x + 1 : null;
let bottom = x => x < 6 ? x + 3 : null;
let move = [left, top, right, bottom];

let swap = (arr, a, b) => {
    let t = arr[a];
    arr[a] = arr[b], arr[b] = t;
}

let bfs = arr => {
    let queue = [[arr, arr.indexOf('x')]];//存放当前网格状态与x位置
    let step = -1;
    while (queue.length > 0) {
        step++;
        let next = [];
        for (let i = 0; i < queue.length; i++) {
            let act = queue[i][0].join('');
            let x = queue[i][1];
            if (dic.has(act)) continue; //去重
            if (act === target) return step;
            dic.add(act);
            for (let j = 0; j < 4; j++) { //4个方向
                let y = move[j](x);
                if (y !== null) {
                    let copy = [].concat(queue[i][0]);
                    swap(copy, x, y);
                    next.push([copy, y]);
                }
            }
        }
        queue = next;
    }
    return -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) {
            let a = getInputStr(line);
            console.log(bfs(a));
        }
    });
});




gaobowen
6个月前

思路:广度搜索+去除重复步骤

//存放走过了的方案
let dic = new Set();
const target = '12345678x';

let left = x => x % 3 ? x - 1 : null;
let top = x => x >= 3 ? x - 3 : null;
let right = x => x % 3 < 2 ? x + 1 : null;
let bottom = x => x < 6 ? x + 3 : null;
let move = [left, top, right, bottom];

let swap = (arr, a, b) => {
    let t = arr[a];
    arr[a] = arr[b], arr[b] = t;
}

let bfs = arr => {
    let queue = [[arr, arr.indexOf('x')]];//存放当前网格状态与x位置
    let step = -1;
    while (queue.length > 0) {
        step++;
        let next = [];
        for (let i = 0; i < queue.length; i++) {
            let act = queue[i][0].join('');
            let x = queue[i][1];
            if (dic.has(act)) continue; //去重
            if (act === target) return step;
            dic.add(act);
            for (let j = 0; j < 4; j++) { //4个方向
                let y = move[j](x);
                if (y !== null) {
                    let copy = [].concat(queue[i][0]);
                    swap(copy, x, y);
                    next.push([copy, y]);
                }
            }
        }
        queue = next;
    }
    return -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) {
            let a = getInputStr(line);
            console.log(bfs(a));
        }
    });
});



活动打卡代码 AcWing 844. 走迷宫

gaobowen
6个月前
let n = 0, m = 0;//n行,m个整数
let map = [];
let way = [];//保存走过的路径

//上右下左
let dx = [0, 1, 0, -1];
let dy = [-1, 0, 1, 0];

let bfs = () => {
    let queue = []; //存放坐标
    queue.push([0, 0]);
    map[0][0] = 1;//起点需要被标记
    let step = 0;
    while (queue.length > 0) {
        step++;
        let k = queue.length;
        for (let i = 0; i < k; i++) { //一次取完当前步骤
            let top = queue.shift();
            for (let j = 0; j < 4; j++) { //寻找4个方向
                let x = top[0] + dx[j];
                let y = top[1] + dy[j];
                if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] === 0) {
                    map[x][y] = 1;
                    queue.push([x, y]);
                    way[x][y] = top;//存放当前步骤的前一步
                }
                if (x === n - 1 && y === m - 1) {
                    console.log(step);
                    //printWay(x,y)
                    return;
                }
            }
        }
    }
}

let printWay = (x, y) => {
    let curr = [x, y];
    while (curr) {
        console.log(curr);
        curr = way[curr[0]][curr[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) {
            let a = getInputNums(line);
            n = a[0], m = a[1];
        } else if (lineIdx <= n) {
            map.push(getInputNums(line));
            way.push([]);
            if(lineIdx === n)
                bfs();
        }
    });
});



gaobowen
6个月前
let n = 0, m = 0;//n行,m个整数
let map = [];
let way = [];//保存走过的路径

//上右下左
let dx = [0, 1, 0, -1];
let dy = [-1, 0, 1, 0];

let bfs = () => {
    let queue = []; //存放坐标
    queue.push([0, 0]);
    map[0][0] = 1;//起点需要被标记
    let step = 0;
    while (queue.length > 0) {
        step++;
        let k = queue.length;
        for (let i = 0; i < k; i++) { //一次取完当前步骤
            let top = queue.shift();
            for (let j = 0; j < 4; j++) { //寻找4个方向
                let x = top[0] + dx[j];
                let y = top[1] + dy[j];
                if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] === 0) {
                    map[x][y] = 1;
                    queue.push([x, y]);
                    way[x][y] = top;//存放当前步骤的前一步
                }
                if (x === n - 1 && y === m - 1) {
                    console.log(step);
                    //printWay(x,y)
                    return;
                }
            }
        }
    }
}

let printWay = (x, y) => {
    let curr = [x, y];
    while (curr) {
        console.log(curr);
        curr = way[curr[0]][curr[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) {
            let a = getInputNums(line);
            n = a[0], m = a[1];
        } else if (lineIdx <= n) {
            map.push(getInputNums(line));
            way.push([]);
            if(lineIdx === n)
                bfs();
        }
    });
});