PAT1052

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1052shui

水题一道，注意3点（题目没说清楚2,3）

（1）题目中可能存在多条链表。我们只要其中一条。

（2）如果给出的起始节点的地址为-1，则输出“0 -1”。

（3）如果根据给出的起始节点的地址无法找到一条链表，则输出“0 起始节点地址”。

 1 #include<cstdio>
 2 #include<vector>
 3 #include<iomanip>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct Node
 8 {
 9     int address;
10     int key;
11     int next;
12 };
13 
14 struct Record
15 {
16     int key;
17     int next;
18 }empty={0,-2};
19 
20 bool comp(Node n1, Node n2)
21 {
22     if(n1.key < n2.key)
23         return true;
24     else
25         return false;
26 }
27 
28 int main()
29 {
30     int N,start;
31     while(scanf("%d%d",&N, &start) != EOF)
32     {
33             vector<Record> v(100000, empty);
34             for(int i=0; i<N; ++i)
35             {
36                 int a,b,c;scanf("%d%d%d",&a, &b, &c);
37                 v[a].key=b; v[a].next=c;
38             }
39             if(start == -1)
40                 printf("0 -1
");
41             else if(v[start].next == -2)
42                 printf("0 %05d
", start);
43             else
44             {
45                 vector<Node> inlist;
46                 while(start != -1)
47                 {
48                     if(v[start].next == -2)
49                         break;
50                     Node n={start, v[start].key, v[start].next};
51                     inlist.push_back(n);
52                     start = v[start].next;
53                 }
54                 sort(inlist.begin(), inlist.end(), comp);
55                 int length = inlist.size();
56                 for(int i=0; i<length-1; ++i)
57                     inlist[i].next = inlist[i+1].address;
58                 printf("%d %05d
", length, inlist[0].address);
59                 for(int i=0; i<length-1; ++i)
60                     printf("%05d %d %05d
", inlist[i].address, inlist[i].key, inlist[i].next);
61                 printf("%05d %d -1
", inlist[length-1].address, inlist[length-1].key);
62             }
63     }
64     return 0;
65 }