[C++知识库]leetcode 332. 重新安排行程 （回溯/DFS）c++ 2021-07-13

//恶心哦

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) 
    {
        int ticketNum = tickets.size() + 1;
        for (const vector<string>& target : tickets)
        {
            airports[target[0]][target[1]]++;
        }
        result.push_back("JFK");
        backTracking(result, ticketNum);
        return result;
    }
    
private:
    vector<string> result;
    unordered_map<string, map<string, int>> airports;
    bool backTracking(vector<string> &result, int ticketNum);
};

inline bool Solution::backTracking(vector<string> &result, int ticketNum)
{
    if (result.size() == ticketNum)
    {
        return true;
    }

    for (auto &x : airports[result[result.size() - 1]])
    {
        if (x.second > 0)
        {
            result.push_back(x.first);
            x.second--;
            if (backTracking(result, ticketNum))
                return true;
            x.second++;
            result.pop_back();
        }
    }
    return false;
}