332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return ["JFK", "MUC", "LHR", "SFO", "SJC"]. Example 2: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return ["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目的意思是规划行程，给定若干机票，将机票中的行程走完。

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        for(auto ticket:tickets)
            targets[ticket.first].insert(ticket.second);

        visit("JFK");

        return vector<string> (route.rbegin(), route.rend());
    }
private:
    map<string, multiset<string>> targets;
    vector<string> route;

    void visit(string start){
        string next;

        while(targets[start].size()){
            next = *targets[start].begin();
            targets[start].erase(targets[start].begin());
            visit(next);
        }
        route.push_back(start);
    }
};