leetcode-2368.png

这一题也是典型的遍历然后剪枝的过程
我用BFS来解决这题，但是没能ac，超时了
下面来展示下代码

var reachableNodes = function (n, edges, restricted) {
    let res = []
    // queue 来存放下次要访问的节点列表
    let queue = []
    // visited 存放已经访问过的 edge
    let visited = new Set()
    edges.forEach(el => {
        if (el.indexOf(0) > -1) {
            let index = el.indexOf(0) === 0 ? 1 : 0
            queue.push(el[index])
            visited.add(el)
        }
    })
    while (queue.length) {
        let size = queue.length
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            // 剪枝，如果在 restricted 里面没出现过，则再来处理当前节点的邻接节点
            if(!restricted.includes(node)){
                res.push(node)
                for(let edge of edges){
                    // 找出没有访问过的邻接节点，然后标记，并把邻接节点放入queue中
                    if(edge.includes(node) && !visited.has(edge)){
                        let index = edge.indexOf(node) === 0 ? 1 : 0
                        queue.push(edge[index])
                        visited.add(edge)
                    }
                }
            }
        }
    }
    return res.length + 1
};

构建邻接表

这里的思路其实也是一样的BFS，但是用了邻接表

var reachableNodes = function (n, edges, restricted) {
    let res = 0
    let visited = new Set()
    let restrict = new Set(restricted)
    let graph = new Map()
    // 构建邻接表
    for (let [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, [])
        if (!graph.has(v)) graph.set(v, [])
        graph.get(u).push(v)
        graph.get(v).push(u)
    }
    let queue = []
    queue.push(0)
    visited.add(0)
    while (queue.length) {
        let node = queue.shift()
        res++
        // 在邻接表里面遍历未访问过以及未限制的元素
        for (let g of graph.get(node)) {
            if (!visited.has(g) && !restrict.has(g)) {
                queue.push(g)
                visited.add(g)
            }
        }
    }
    return res
};