【备战秋招】每日一题:2023-04-19-华为OD(第二题)-塔子哥出城

在线评测链接:P1196

题目内容

塔子哥居住在数据结构之城，如果将这个城市的路口看做点，两个路口之间的路看做边，那么该城市的道路能够构成一棵由市中心路口向城市四周生长的树，树的叶子节点即是出城口。

塔子哥今天想要出城办事，但不巧的是，有几个路口堵车了，塔子哥无法从一个正常的路口前往堵车的路口。假定塔子哥从一个正常的路口出发，请问塔子哥能否顺利出城（到达出城口）？如果可以，请帮塔子哥找到最省油的路径（经过路口最少的路径），否则请输出“ $N ULL$ ”。

输入描述

第一行给出数字 $n$ ，表示这个城市有 $n$ 个路口，路口从 $0$ 开始依次递增， $0$ 固定为根节点， $1\leq n<10000$

第二行给出数字 $m$ ，表示接下来有 $m$ 行，每行是一条道路

接下来的 $m$ 行是边: $x ， y$ ，表示x和 $y$ 路口有一条道路连接。保证是一颗树

道路信息结束后接下来的一行给出数 $d$ ，表示接下菜有 $d$ 行，每行是一个堵车的路口

接下来的 $d$ 行是堵车路口 $k$ ，表示路口 $k$ 已堵车

输出描述

如果塔子哥能够顺利出城，请输出塔子哥能够到达任意一个出城口的最短路径（通过路口最少），比如塔子哥从 $0$ 经过 $1$ 到达 $2$ (出城口) ，那么输出“ $0 - > 1 - > 2$ ”;否则输出“ $N ULL$ ”。注意如果存在多条最短路径，请按照节点序号排序输出，比如$ 0->1$ 和 $0 - > 3$ 两条路径，第一个节点 $0$ 一样，则比较第二个节点 $1$ 和 $3$ ， $1$ 比 $3$ 小，因此输出 $0 - > 1$ 这条路径。再如 $0 - > 5 - > 2 - > 3$ 和 0->5->1->4，则输出 $0 - > 5 - > 1 - > 4$ 。

样例

输入

输出

0->1

说明

$n = 4$ , $e d g e = [[0, 1], [0, 2], [0.3]$ , $b l oc k = [2, 3]]$ 表示一个有 $4$ 个节点， $3$ 条边的树，其中节点 $2$ 和节点 $3$ 上有障碍物，小猴子都能从 $01$ 到达叶子节点 $1$ （节点1只有一条边 $[0, 1]$ 和它连接，因此也是叶子节点），即可以跑出这个树，所以输出为 $0 - > 1$ .

样例2

输入

输出

0->1->2

说明

节点 $4$ 上有障碍物，因此 $0 - 3 - 4$ 这条路不通，节点 $2$ 和节点 $6$ 都是叶子节点，但 $0 - > 1 - > 2$ 比 $0 - > 1 - > 5 - > 6$ 路径短 (通过的边最少) ，因此输出为 $0 - > 1 - > 2$ 。

思路

树上dfs/bfs

题意化简:给定一棵树，其中有些点无法访问。需要找一条从根节点到叶子结点的路径，要求满足长度最短且字典序最小。

做法1:dfs

直接dfs，在这个过程中存储好已访问的路径。然后遇到叶子结点就用当前路径更新答案路径。

这样做的复杂度是 $O(n+\sum depth(leaf\quad node))$ ，其中第一项来自于dfs的开销，第二项来自于 <在叶子结点的记录答案>的开销。但这里塔子哥不太会估计第二项的上界。感觉上是去构造一颗完全二叉树，这样复杂度是 $O (n l o g n)$ 的

做法2:bfs

由于要满足长度最短，所以想到bfs也是比较自然的。对于字典序最小的性质，我们只需要对同一层的结点编号进行升序排序即可。复杂度 $O (n l o g n)$

类似题目推荐

LeetCode

112. 路径总和
129. 求根到叶子节点数字之和
236. 二叉树的最近公共祖先

CodeFun2000

1.P1224 携程 2023.04.15-春招-第三题-魔法之树

2.P1159. 2022年清华大学(深圳)保研夏令营机试题-第一题-树上计数

3.P1196 华为 2023-04-19-第二题-塔子哥出城

4.P1044. 拼多多内推笔试-2023.2.22.投喂珍珠

5.P1193. 腾讯音乐 2023.04.13-暑期实习-第二题-价值二叉树

更多请见:知识点分类-训练-深度优先搜索专栏

代码

以下皆为 $D FS$ 做法。 $BFS$ 做法见题解区

CPP

#include<bits/stdc++.h>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> edges;
vector<int> blocks;
vector<int> path;  // 当前路径
vector<int> res; // 答案路径
int tmp = INT_MAX;
vector<bool> used; // 标记是否被访问.
bool judge = false;
// idx 为当前所在点 , num 为深度
void dfs(int idx, int num){
    // 到叶子节点，更新答案
    if(edges[idx].size() == 0){
        if(num < tmp){
            tmp = num;
            res = path;
        }
        judge = true;
    }
    //对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
    sort(edges[idx].begin(), edges[idx].end());
    // 递归
    for(auto & a : edges[idx]){
        if(blocks[a] == 0 && used[a] == false){
            used[a] = true;
            path.push_back(a);
            dfs(a, num + 1);
            path.pop_back();
            used[a] = false;
            }
        }
} 
int main(){
    // 读入
    cin >> n >> m;
    edges.resize(n + 1);
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
    }
    // 标记 不能访问的点
    int k;
    cin >> k;
    blocks.resize(n + 1, 0);
    for(int i = 0; i < k; i ++){
        int k1;
        cin >> k1;
        blocks[k1] = 1;
    }
    used.resize(n + 1, false);
    path.push_back(0);
    used[0] = true;
    // dfs
    dfs(0, 1);
    // 输出
    if(judge){
        for(int i = 0; i < res.size(); i ++){
            cout << res[i];
        if(i != res.size() - 1){
            cout << "->";
        }
     }
    }
    else cout << "NULL" << endl;
    return 0;
}

python_195">python

python">import sys

# 递归函数，idx 表示当前所在的节点，num 表示深度
def dfs(idx: int, num: int):
    global tmp, path, res, judge
    # 到达叶子节点，更新答案
    if not edges[idx]:
        if num < tmp:
            tmp = num
            res = path.copy() #列表复制
        judge = True
    # 对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
    edges[idx].sort()
    # 递归搜索子节点
    for a in edges[idx]:
        if (blocks[a] == 0 and not used[a]):
            used[a] = True
            path.append(a)
            dfs(a, num + 1)
            path.pop() # 回溯
            used[a] = False
			
# 读入
n = int(input())
m = int(input())
edges = [[] for i in range(n+1)]
for i in range(m):
	a, b = map(int, sys.stdin.readline().strip().split())
	edges[a].append(b)
# 标记不能访问的点
k = int(sys.stdin.readline().strip())
blocks = [0] * (n + 1)
for i in range(k):
	k1 = int(sys.stdin.readline().strip())
	blocks[k1] = 1
used = [False] * (n + 1)
path = [0]
used[0] = True
# dfs
tmp = 0x7fffffff # 设置一个最大值
res = []
judge = False
dfs(0, 1)
# 输出
if judge:
	for i in range(len(res)):
		print(res[i], end='')
		if i != len(res) - 1:
			print("->", end='')
else:
	print("NULL", end='')

Java

java">import java.util.*;

class Main {
    static int ans=Integer.MAX_VALUE/2;
    static ArrayList<Integer> path=new ArrayList<>();
    static ArrayList<Integer> []map;
    static boolean []arrive;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt();
        //邻接表
        map=(ArrayList<Integer>[]) new ArrayList<?>[n];
        for(int i=0;i<n;i++){
            map[i]=new ArrayList<Integer>();
        }
        int m=sc.nextInt();

        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            map[a].add(b);
        }
        // 每个节点的子节点排序
        for(int i=0;i<n;i++){
            if(map[i].size()!=0){
                Collections.sort(map[i]);
            }
        }
        
        int k=sc.nextInt();

        //每个点是否可达
        arrive=new boolean[n];
        Arrays.fill(arrive, true);
        for(int i=0;i<k;i++){
            arrive[sc.nextInt()]=false;
        }
        // dfs求解
        ArrayList<Integer> cur_path=new ArrayList<>();
        cur_path.add(0);
        dfs(0,cur_path);

        if(ans!=Integer.MAX_VALUE/2){
            for(int i=0;i<path.size()-1;i++){
                System.out.printf("%d->",path.get(i));
            }
            System.out.println(path.get(path.size()-1));
        }else{
            System.out.println("NULL");
        }

    }

    public static void dfs(int cur_node,ArrayList<Integer> cur_path){
        // 叶子节点更新答案
        if(cur_path.size()>ans){
            return;
        }
        if(map[cur_node].size()==0 && cur_path.size()!=0 && cur_path.size()<ans){
            ans=Math.min(ans, cur_path.size());
            path=new ArrayList<>(cur_path);
            return;
        }
        // 递归搜索
        for(int i=0;i<map[cur_node].size();i++){
            int next_node=map[cur_node].get(i);
            if(arrive[next_node]){
                cur_path.add(next_node);
                dfs(next_node,cur_path);
                cur_path.remove(cur_path.size()-1);
            }
            
        }
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var (
	edges  [][]int
	blocks []int
	used   []bool
	path   []int
	tmp    int
	res    []int
	judge  bool
)
// dfs
func dfs(idx int, num int) {
    // 到叶子节点，更新答案
	if len(edges[idx]) == 0 {
		if num < tmp {
			tmp = num
			res = append([]int(nil), path...) // slice复制
		}
		judge = true
	}
    //对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
	sort.Ints(edges[idx])
	for _, a := range edges[idx] {
		if blocks[a] == 0 && !used[a] {
			used[a] = true
			path = append(path, a)
			dfs(a, num+1)
			path = path[:len(path)-1]
			used[a] = false
		}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)

	var n, m , k int
	fmt.Fscan(in, &n)
	fmt.Fscan(in, &m)

	edges = make([][]int, n+1)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		edges[a] = append(edges[a], b)
	}

	fmt.Fscan(in, &k)

	blocks = make([]int, n+1)
	for i := 0; i < k; i++ {
		var k1 int
		fmt.Fscan(in, &k1)
		blocks[k1] = 1
	}

	used = make([]bool, n+1)
	path = []int{0}
	used[0] = true

	tmp = 0x7fffffff
	dfs(0, 1)

	if judge {
		for i := 0; i < len(res); i++ {
			fmt.Printf("%d", res[i])
			if i != len(res)-1 {
				fmt.Printf("->")
			}
		}
	} else {
		fmt.Println("NULL")
	}
}

Js

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 结点总数 例如 4个节点 即 0 - 3
    let nodeTotal = Number(await readline())
    // 0 - 3  头节点
    let edges = new Array(nodeTotal)
    for(let i = 0; i < nodeTotal ; i++){
        edges[i] = []
    }
    // 这边先读取变，然后 sort一下
    // 前者小的在前 ，后者在前面的基础上 也小的在前
    let edgeNum = Number(await readline())
    let edgeArr = []
    for(let i = 0; i < edgeNum; i++)
        edgeArr.push((await readline()).split(" ").map(Number))
    // sort
    edgeArr.sort((a, b) => {
        if (a[0] === b[0]) {
          return a[1] - b[1];
        }
        return a[0] - b[0];
    });
    for(let i = 0; i < edgeNum; i++){
        let [beginNode, endNode] = edgeArr[i]
        edges[beginNode].push(endNode)
    } 
    // 有几条边 例如 3条

 // 禁止的节点个数
 let forbiddenNum = Number(await readline())
 // let forbiddenNodes = []
 let forbiddenNodes = new Array(nodeTotal).fill(true)
 // 这些点被禁用 存储一下
 for(let j = 0; j < forbiddenNum; j++)
     forbiddenNodes[Number(await readline())] = false
 
 let temp = []
 let minLen = Infinity
 let result = ""
 function dfs(currNode){
     temp.push(currNode)
     let useEdge = edges[currNode]
     let useEdgeFilter = useEdge.filter( node => forbiddenNodes[node])
     // 叶子节点更新答案
     if(useEdge.length == 0){
         if(minLen > temp.length){
             minLen = temp.length
             result = temp.join("->")
         }
         return;
     }
     // 递归搜索
     for(let i = 0; i < useEdgeFilter.length; i++){
         dfs(useEdgeFilter[i])
         temp.pop()
     }
 }
 dfs(0)
 if(minLen == Infinity)
     console.log("NULL")
 else
     console.log(result)
}()
// by kaikaichaoren2