Share my solution


  • 95

    See also here

    All the airports are vertices and tickets are directed edges. Then all these tickets form a directed graph.

    The graph must be Eulerian since we know that a Eulerian path exists.

    Thus, start from "JFK", we can apply the Hierholzer's algorithm to find a Eulerian path in the graph which is a valid reconstruction.

    Since the problem asks for lexical order smallest solution, we can put the neighbors in a min-heap. In this way, we always visit the smallest possible neighbor first in our trip.

    public class Solution {
    
        Map<String, PriorityQueue<String>> flights;
        LinkedList<String> path;
    
        public List<String> findItinerary(String[][] tickets) {
            flights = new HashMap<>();
            path = new LinkedList<>();
            for (String[] ticket : tickets) {
                flights.putIfAbsent(ticket[0], new PriorityQueue<>());
                flights.get(ticket[0]).add(ticket[1]);
            }
            dfs("JFK");
            return path;
        }
    
        public void dfs(String departure) {
            PriorityQueue<String> arrivals = flights.get(departure);
            while (arrivals != null && !arrivals.isEmpty())
                dfs(arrivals.poll());
            path.addFirst(departure);
        }
    }
    
    79 / 79 test cases passed.
    Status: Accepted
    Runtime: 11 ms

  • 1

    Beautiful! But I have a confusion with your explanation about Eulerian Graph. I searched on Google, it shows that Eulerian Graph is the graph whose each node is visited exactly once. Based on the example 2 of question's statement, circle is not checked(["JFK","ATL","JFK","SFO","ATL","SFO"]), so I was wondering if you would better remove words corresponding to Eulerian. Correct me if I am wrong. BTW, your code is always clean and nice! Thank you!


  • 17

    I am pretty sure that Eulerian graph means visit each "EDGE" once and only once.

    The one that visited each node once and only once is called Hamiltonian.


  • 1

    got it, thank you!


  • 6

    Thanks for mention Eulerian path and Hierholzer's algorithm, studying this background really helped me making clear this problem, as I was very confused how those non-backtracking solutions could work... Thank you.
    BTW, Hierholzer's algorithm can only be applied on Eulerian cycle, while for Eulerian path problems, one should consider Fleury's algorithm (wiki)


  • 0
    S

    if the case is [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"], ["JFK", "ZTL"]]
    what is the result? thanks


  • 0

    Great solution. I found an explanation on another topic.
    https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c/13


  • 0

    This is beautiful! Add from the vertex which has no arrivals


  • 1

    Someone down voted my reply, did I say any thing wrong? Please help pointing out, thanks.


  • 0
    B
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    B

    @dietpepsi Elegant!


  • 0
    M

    I have pretty much the same idea implemented in C++, though min heap is a bit lengthy in C++.

    class Solution {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            deque<string> ret;
            unordered_map<string, priority_queue<string, vector<string>, greater<string>>> M;
            for (auto &pair : tickets) {
                M[pair.first].push(pair.second);
            }
            
            string start("JFK");
            DFS(M, ret, start);
            return vector<string> (ret.begin(), ret.end());
        }
        
        void DFS(unordered_map<string, priority_queue<string, vector<string>, greater<string>>> &M, deque<string> &ret, string &cur) {
            while (!M[cur].empty()) {
                string next = M[cur].top();
                M[cur].pop();
                DFS(M, ret, next);
            }
            ret.push_front(cur);
        }
    };
    

  • 1
    J

    why we use a while loop here instead of using if?


  • 2
    L

    From this link http://www.geeksforgeeks.org/euler-circuit-directed-graph/, I found the following definition of a Eulerian graph.

    How to check if a directed graph is eulerian?
    A directed graph has an eulerian cycle if following conditions are true (Source: Wiki)

    1. All vertices with nonzero degree belong to a single strongly connected component.
    2. In degree and out degree of every vertex is same.

    In your post, you say that it is sured that the graph is Eulerian, take this test case for example.
    [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

    The indegree of "JFK" is zero, the outdegree of "JFK" is one, I believe this will contradict the rule 2) given above, so it is not Eulerian. Please correct me if I am wrong. Thank you!


  • 0
    L

    @LeonCheng Apologies. I was wrong, the definition is about Eulerian Cycle, not Eulerian directed graph.


  • 0
    C

    excellent solution, thx


  • 6
    O

    Hi, I am wondering how do you make sure there is no dead end since you always choose the "smallest" arrivals (min heap). Thanks.


  • 4
    W

    @Oliiiviiiaaa Starting at the first node, we can only get stuck at the ending point, since every node except for the first and the last node has even number of edges, when we enter a node we can always get out. Now we are at the destination and if all edges are visited, we are done, and the dfs returns to the very first state. Otherwise we need to "insert" the unvisited loop into corresponding position, and in the dfs method, it returns to the node with extra edges, starts another recursion and adds the result before the next path. This process continues until all edges are visited.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.