【图论】图的遍历 - 构建领接表（无向图）

例题：受限条件下可到达节点的数目

题目链接：2368. 受限条件下可到达节点的数目

题目描述

代码与注释

func reachableNodes(n int, edges [][]int, restricted []int) (ans int) {r := make(map[int]bool, len(restricted))for _, v := range restricted {r[v] = true // 把受限的节点设置为 true}g := make([][]int, n)for _, v := range edges { // 建邻接表x, y := v[0], v[1]if r[x] == false && r[y] == false {g[x] = append(g[x], y)g[y] = append(g[y], x)}}var dfs func(int, int)dfs = func(x, father int) { // dfs 邻接表存储的图ans++for _, v := range g[x] {if v != father { // 避免回溯到父节点导致重复遍历dfs(v, x)}}}dfs(0, -1) // 从 0 1 开始return ans
}

模板抽象

建邻接表

for _, v := range edges { // 建邻接表x, y := v[0], v[1]g[x] = append(g[x], y)g[y] = append(g[y], x)
}

通过领接表 dfs 图

var dfs func(int, int)
dfs = func(x, father int) { // dfs 邻接表存储的图for _, v := range g[x] {if v != father { // 避免回溯到父节点导致重复遍历dfs(v, x)}}
}
dfs(0, -1) // 从 0 1 开始