Powered by:NEFU AB-IN

Link

693. 行程排序

• 题意

  玛丽需要从某地飞往另一目的地，由于没有直达飞机，所以需要在中途转很多航班。
  例如：SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD。
  显然旅途中不可能到同一中转城市两次或以上，因为这没有意义。
  不幸的是，她将自己的机票的顺序搞乱了，将机票按乘坐顺序整理好对她来说不是一件容易的事。
  请你帮助玛丽整理机票，使机票按正确顺序排列。

• 思路

  哈希，链表输出即可

• 代码

  /* * @Author: NEFU AB-IN * @Date: 2022-08-04 16:35:04 * @FilePath: \Acwing\693\693.cpp * @LastEditTime: 2022-08-04 16:42:55 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
        
      IOS;
      int T;
      cin >> T;
      for (int _ = 1; _ <= T; ++_)
      {
        
          int n;
          cin >> n;
          map<string, string> st;
          map<string, int> deg;
          set<string> se;
          for (int i = 1; i <= n; ++i)
          {
        
              string s, t;
              cin >> s >> t;
              st[s] = t;
              deg[t]++;
              se.insert(s), se.insert(t);
          }
  
          string s;
          for (auto c : se)
          {
        
              if (!deg[c])
                  s = c;
          }
          printf("Case #%lld: ", _);
  
          while (st.count(s))
          {
        
              printf("%s-%s ", s.c_str(), st[s].c_str());
              s = st[s];
          }
          puts("");
      }
      return 0;
  }