c++ topology sort using priority_queue


  • 0
    J

    This question is quite similar with Course Schedule I, II and Minimum Height Tree.

     class Solution {
      public:
    	  vector<string> findItinerary(vector<pair<string, string>> tickets) {
    		  int len = tickets.size();
    		  unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> graph;
    		  //construct the graph
    		  for (auto ticket : tickets)
    		  {
    			  graph[ticket.first].push(ticket.second);
    		  }
    		  vector<string> iternary;
    		  stack<string> route;
    		  route.push("JFK");
    		  while (!route.empty())
    		  {
    			  string city = route.top();
    			  if (graph[city].empty())
    			  {
    				  iternary.push_back(city);
    				  route.pop();
    			  }
    			  else
    			  {
    				  route.push(graph[city].top());
    				  graph[city].pop();
    			  }
    		  }
    		  std::reverse(iternary.begin(), iternary.end());
    		  return iternary;
    	  }
      };
    

Log in to reply
 

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