### LeetCode June Challenge - Day 28

Problem: LeetCode June Challenge - Day 28

Ideas

1. Find an Eulerian Path in the graph given.
2. Here are some implementation details:
• I used a hash map to store the graph, so I didn’t need to assign integers to the strings.
• For each vertex I store a vector with the possible destinations. I also store in a hash map theindex of the last vertex I visited, which simulates deleting edges.

Solution:

``````class Solution {
unordered_map<string, vector<string>> m;
unordered_map<string, int> index;
vector<string> ans;
string start = "JFK";

void construct_graph(vector<vector<string>>& tickets){
for(vector<string>& f : tickets)
m[f[0]].push_back(f[1]);
for(auto& p : m)
sort(p.second.begin(), p.second.end());
}

void dfs(const string& u){
while(index[u] < m[u].size()){
string v = m[u][index[u]++];
dfs(v);
}
ans.push_back(u);
}

public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
construct_graph(tickets);
dfs(start);
reverse(ans.begin(), ans.end());
return ans;
}
};
``````