团体程序设计天梯赛PTA L2-002链表去重

题意：给定一个带整数键值的链表
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<math.h>
 8 using namespace std;
 9 const int N = 1e5 + 10;
10 int vis[N];
11 queue<int> q1;//存下去重的链表元素地址
12 queue<int> q2;//存下被删除的元素地址
13 struct node
14 {
15     int from;
16     int to;
17     int w;
18     int next;
19 } no[N];//用链表形式储存
20 void init()
21 {
22     memset(vis,0,sizeof(vis));
23 }//初始化
24 int main()
25 {
26     int head, n, a;
27     scanf("%d%d",&head,&n);
28     init();
29     for(int i = 1; i <= n; i ++)
30     {
31         scanf("%d",&a);
32         scanf("%d%d",&no[a].w,&no[a].next);
33         no[a].from = a;
34     }
35     for(int i = head; i != -1; i = no[i].next)
36     {
37         if(vis[abs(no[i].w)] == 0)
38         {
39             vis[abs(no[i].w)] = 1;
40             q1.push(no[i].from);
41         }
42         else
43         {
44             q2.push(no[i].from);
45         }
46     }
47     /*
48          输出部分需要注意，
49          题目要求去重后的链表和删除的链表变成了两个链表，
50          所以有两个尾巴（标记为-1）
51          输出部分用queue队列输出
52     */
53     int flag1 = q1.front(),flag2 = q2.front() ;
54     int n1 = q1.size(), n2 = q2.size();
55     while(!q1.empty())
56     {
57         if(n1 > 1)
58         {
59             printf("%05d %d",no[flag1].from,no[flag1].w);
60             q1.pop();
61             flag1 = q1.front();
62             printf(" %05d
",no[flag1].from);
63         }
64         else
65         {
66             printf("%05d %d -1
",no[flag1].from,no[flag1].w);
67             break;
68         }
69         n1--;
70 
71     }
72     while(!q2.empty())
73     {
74         if(n2 > 1)
75         {
76             printf("%05d %d ",no[flag2].from,no[flag2].w);
77             q2.pop();
78             flag2 = q2.front();
79             printf("%05d
",no[flag2].from);
80         }
81 
82         else
83         {
84             printf("%05d %d -1
",no[flag2].from,no[flag2].w);
85             break;
86         }
87         n2--;
88     }
89     return 0;
90 }