ID: 9

Difficulty: 7

题目内容

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

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

输入描述

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

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

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

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

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

输出描述

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

样例

样例1

输入

输出

0->1

说明

n=4, edge=[[0,1],[0,2], [0.3], block=[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

1.数据结构选择：

使用邻接表来表示树的结构，其中每个节点连接的路口作为其邻居。

2.输入处理：

读取城市的路口数、道路数及其连接信息，构建树的邻接表。读取堵车路口的信息，并使用一个布尔数组标记这些堵车路口。

3.深度优先搜索（DFS）：

从根节点开始进行 DFS，寻找所有可能的出城口（叶子节点）。在 DFS 的过程中，忽略被堵车的路口。对于每次到达叶子节点，记录当前路径并更新最优路径（经过路口最少且字典序最小）。

4。路径记录和输出：

如果找到有效的出城路径，输出该路径；如果没有找到，则输出“NULL”。

做法2:bfs

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

代码说明

1.输入读取：

读取节点数和边数，构建树的邻接表。读取堵车路口并进行标记。

2.DFS 初始化：

使用一个数组记录当前路径。使用一个布尔数组标记已经访问的节点。

3.DFS 遍历：

对当前节点进行遍历，检查邻接节点。如果邻接节点没有堵车且没有被访问，继续深入 DFS。如果到达叶子节点，记录当前路径并更新最优路径。

4.输出结果：

如果找到路径，格式化并输出路径；否则，输出“NULL”。

代码

以下皆为 $DFS$ 做法。 $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


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

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

#P1580. 2023.4.19-暑期实习-第二题-小红出城

2023.4.19-暑期实习-第二题-小红出城