当前位置：网站首页>leetcode：332. 重新安排行程

leetcode：332. 重新安排行程

2022-08-09 22:01:00 【OceanStar的学习笔记】

在这里插入图片描述

class Solution {
    
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
    

    }
};

分析数据量

题意

在这里插入图片描述

给你一沓机票，用它去飞（遍历）图中的城市（节点），机票要用光（遍历完所有的边），返回出访问城市的路径，且机票不能重复用（遍历过的边要拆掉）。

题意说，用完机票所走的路径一定存在，找出一条即可。没找到用完机票的路径就是：你困在一个城市，手里有不合适的机票，用不出去。对应到图就是，到了一个点，没有邻接点能访问，但你还有边没遍历。

先构建邻接表，以便能知道可以飞到哪些城市
然后从JTK开始，尝试所有可能的选择，根据当前的选择，往下递归，尝试找出第一个用完机票的路径，如果找不出来，返回false，否则，返回true。
访问过的边要删掉。比如，北京飞广州，到了广州，北京的邻居list中删掉广州。
为什么要返回真假，因为要用它判断要不要提前回溯，在该分支走不下去，就要离开。
我们选择飞入的城市，如果困住了，就是飞错了，要回溯，将北京的邻居list中删除的广州恢复回来，不飞广州了，飞别的试试，离开当前分支，切入别的分支，继续探索路径。