DFS+回溯思想 or Hierholzer 算法：Leetcode332:重新安排行程

问题：

思路：

DFS+回溯思想：

使用map保存邻接表，由于map是基于键值自动排序的，所以解决了要输出自然排序最小的行程组合的问题

map的键类型为string，而值类型不使用vector< string >而是使用map<string,int>，用int保存机票的数量，因为输入中可能出现相同的机票

DFS函数的作用是找到以参数start为起点的满足条件的路径，找到返回TRUE，否则返回FALSE。向DFS函数传参count，count表示已遍历的边数，若所有边均遍历，则DFS返回TRUE。

在路径中添加DFS当前正在访问的节点，已遍历的边数加1，对该节点的邻接表中的元素进行访问，进入循环：

在循环中，机票的数量充当了经典DFS中visited数组的作用，若机票数<=0，则证明该机票已被访问过，跳过该次访问，每次访问将其机票数减1，对该元素调用DFS函数，若返回TRUE，则当前DFS也返回TRUE，证明已找到路径。若返回FALSE，证明须回溯，将该元素的机票数+1，即还原

若遍历完所有该节点邻接表中的元素后，仍未找到路径，则在路径中删除该节点，返回FALSE

在主函数中进行邻接表的建立，并调用DFS函数，注意传递的参数count=-1，这样在最开始访问起点后，count即为0，表示已遍历的边数为0。

在代码中注意基于范围的For循环中，由于要修改元素，应使用for( auto& [ airport,number ] : adjtable[start] ) ，使用&对容器进行遍历

Hierholzer 算法:

Hierholzer 算法描述见欧拉图、欧拉路径、Hierholzer 算法
Hierholzer算法就是证明了一点：当存在欧拉路径时，从合理的起始点无脑dfs遍历，得到的路径一定是欧拉路径。
因为题目规定了一定有欧拉路径，并且起点一定是JFK（所以这个起始点一定是合理的），所以根据Hierholzer算法，可以无脑dfs。

在DFS函数中对节点的邻居进行无脑DFS遍历，遍历过的边进行标记，当遍历完所有相邻节点后（对该节点邻接表中的元素调用DFS函数），当前节点没有可遍历的相邻边，根据Hierholzer 算法的思想，此时该节点在路径中，将其加入路径。

最后将得到的路径逆序输出即可

代码：

DFS+回溯思想：

class Solution {
public:
    typedef unordered_map< string,map<string,int> > table;
    int edge_num;
    vector<string> ans;
    bool dfs( table& adjtable,int count,string start )
    {
        ans.push_back( start );
        count++;
        if( count==edge_num )
            return true;
        for( auto& [ airport,number ] : adjtable[start] )
        {
            if( number<=0 )
                continue;
            number--;
            if( dfs( adjtable,count,airport ) )
                return true;
            number++;
        }
        ans.pop_back();
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        table adjtable;
        for( auto temp:tickets )
        {
            if( adjtable.find( temp[0] )==adjtable.end() )
                adjtable[ temp[0] ]=map<string,int>();
            if( adjtable[ temp[0] ].find( temp[1] )==adjtable[ temp[0] ].end() )
                adjtable[ temp[0] ][ temp[1] ]=0;
            adjtable[ temp[0] ][ temp[1] ]++;
        }
        edge_num=tickets.size();
        dfs( adjtable,-1,"JFK" );
       return ans;
    }
};

Hierholzer 算法:

class Solution {
public:
    typedef unordered_map< string,map<string,int> > table;
    vector<string> ans;
    void dfs( table& adjtable,string start )
    {
        for( auto& [ airport,number ] : adjtable[start] )
        {
            if( number<=0 )
                continue;
            number--;
            dfs( adjtable,airport );
        }
        ans.push_back( start );
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        table adjtable;
        for( auto temp:tickets )
        {
            if( adjtable.find( temp[0] )==adjtable.end() )
                adjtable[ temp[0] ]=map<string,int>();
            if( adjtable[ temp[0] ].find( temp[1] )==adjtable[ temp[0] ].end() )
                adjtable[ temp[0] ][ temp[1] ]=0;
            adjtable[ temp[0] ][ temp[1] ]++;
        }
        dfs( adjtable,"JFK" );
        reverse( ans.begin(),ans.end() );
        return ans;
    }
};