2368. 受限条件下可到达节点的数目

2368. 受限条件下可到达节点的数目

• 难度: medium
• 原始链接: https://leetcode.cn/problems/reachable-nodes-with-restrictions
• 标签: 深度优先遍历

解法一: 深度优先遍历

go

func reachableNodes(n int, edges [][]int, restricted []int) int {
  tree := make(map[int][]int)
  for _, edge := range edges {
    tree[edge[0]] = append(tree[edge[0]], edge[1])
    tree[edge[1]] = append(tree[edge[1]], edge[0])
  }
  set := make(map[int]bool, len(restricted))
  for _, num := range restricted {
    set[num] = true
  }
  return dfs(0, -1, tree, set)
}

func dfs(cur, parent int, tree map[int][]int, set map[int]bool) int {
  ans := 1
  for _, next := range tree[cur] {
    if next != parent && !set[next] {
      ans += dfs(next, cur, tree, set)
    }
  }
  return ans
}