题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805369774129152

诶嘿嘿，自己写出来了，没有使用算法笔记的方法，而且感觉自己的方法更简单，其实就是用了一个vector数组，本来一开始想用queue的，后来发现好像没有必要了，而且没有数组方便，

  1. 唯一一个注意点，sort的范围是maxn，不要在validcount中排序

代码

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  6. const int maxn = 100010;
  7. vector<bool> valid(10010, false);
  9. struct Node{
  10.     int address, key, next;
  11.     int order;
  12.     bool flag;
  13. }node[maxn];
  14. vector<Node> v;
  15. bool cmp(Node a, Node b){
  16.     if(a.flag == false || b.flag == false) return a.flag > b.flag;
  17.     else return a.order < b.order;
  18. }
  20. int main(){
  21.     for(int i = 0; i < maxn; i++){
  22.         node[i].flag = false;
  23.         node[i].order = maxn;
  24.     }
  25.     int first, n;
  26.     scanf("%d%d", &first, &n);
  27.     int address, key, next;
  28.     for(int i = 0; i < n; i++){
  29.         scanf("%d%d%d", &address, &key, &next);
  30.         node[address].address = address;
  31.         node[address].key = key;
  32.         node[address].next = next;
  33.     }
  34.     int p = first, validcount = 0;
  35.     while(p != -1){
  36.         if(valid[abs(node[p].key)] == false){
  37.             valid[abs(node[p].key)] = true;
  38.             node[p].flag = true;
  39.             node[p].order = validcount;
  40.             validcount++;
  41.         } else {
  42.             v.push_back(node[p]);
  43.         } 
  44.         p = node[p].next;
  45.     }
  46.     sort(node, node + maxn, cmp);
  47.     for(int i = 0; i < validcount; i++){
  48.         if(i != validcount - 1) printf("%05d %d %05d\n", node[i].address, node[i].key, node[i + 1].address);
  49.         else printf("%05d %d -1\n", node[i].address, node[i].key);
  50.     }
  51.     for(int i = 0; i < v.size(); i++){
  52.         if(i != v.size() - 1) printf("%05d %d %05d\n", v[i].address, v[i].key, v[i + 1].address);
  53.         else printf("%05d %d -1\n", v[i].address, v[i].key);
  54.     }
  55.     return 0;
  56. }