Follow Up: If the starting point of the itinerary is unknown, how can we find the start airport?


  • 0
    M

    For example: the tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]], and how can we find the start airport, that is "JFK"


  • 0
    D

    Search Eular Circuits.


  • 0
    M

    @DriftlessHenry Thanks very much. Based on your reply, I find the solution:
    If all vertices have even degree - choose any of them.
    If there are exactly 2 vertices having an odd degree - choose one of them.
    Otherwise no euler circuit or path exists.

        public List<String> findItinerary(String[][] tickets) {
            List<String> res = new LinkedList<>();
            if(tickets == null || tickets.length == 0 || tickets[0].length == 0) return res;
            Map<String, PriorityQueue<String>> map = new HashMap<>();
            Map<String, Integer> degree = new HashMap<>();
            for(String[] ticket : tickets) {
                if(!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<String>());
                map.get(ticket[0]).offer(ticket[1]);
                degree.put(ticket[0], degree.getOrDefault(ticket[0], 0) + 1);
                degree.put(ticket[1], degree.getOrDefault(ticket[1], 0) + 1);
            }
            String start = findStart(degree);
            //System.out.println("Start Airport: " + start);
            if(start.length() == 0) System.out.println("No path");
            else dfs(res, map, start);
            return res;
        }
        
        private void dfs(List<String> res, Map<String, PriorityQueue<String>> map, String airport) {
            while(map.containsKey(airport) && map.get(airport).size() > 0) {
                dfs(res, map, map.get(airport).poll());
            }
            res.add(0, airport);
        }
        
        private String findStart(Map<String, Integer> map) {
        	boolean allEven = true;
        	String[] res = new String[2];
        	int count = 0;
        	for(String s : map.keySet()) {
        	    int val = map.get(s);
        	    allEven = (val % 2 == 0) && allEven;
        	    if(val % 2 == 1) res[count++] = s;
        	}
        	if(allEven || count == 2) return res[0];
        	else return "";
        }
    

  • 0
    D

    @mysun Exactly! I missed the information that JFK is always the starting city at first, so I tried to solve the problem in this way. Besides Eular Circuits, there are many other interesting circuits topics worth learning.


  • 0
    M

    @DriftlessHenry Yes, last time I also found an interview question about the Eulerian Cycle, if you are interested in, you can try it :)

    Given a password box, its password is a four-digit number, we need to generate a sequence with minimum length to open the password box.

    e.g. if the password is a 3-digit number, and it only contains 0 and 1, then the minimum-length sequence is 0 0 0 1 0 1 1 1 (0 0) , (0 0) means reusing the first and second digit in the sequence, because we can get all the combination: 000, 001, 010, 101, 011, 111, 110, 100,

    (0 0 0) 1 0 1 1 1

    0 (0 0 1) 0 1 1 1

    0 0 (0 1 0) 1 1 1

    0 0 0 (1 0 1) 1 1

    0 0 0 1 (0 1 1) 1

    0 0 0 1 0 (1 1 1)

    0 0 0 1 0 1 (1 1 , 0) 0 0 1 0 1 1 1

    0 0 0 1 0 1 1 (1 , 0 0) 0 1 0 1 1 1

    We can see this sequence is the minimum-length sequence which contains all 3-digit number with 0 and 1.


  • 0
    A
    This post is deleted!

Log in to reply
 

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