正文
ZOJ 4016 Mergeable Stack（from The 18th Zhejiang University Programming Contest Sponsored by TuSimple）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
模拟题，用链表来进行模拟
# include <stdio.h>
# include <stdlib.h>
typedef struct node
{
int num;
struct node *q;
struct node *h;
}node;
struct Node
{
node *start;
node *end;
int sum;
}m[];
int main()
{
int k;
scanf("%d", &k);
while (k--)
{
int n, p;
scanf("%d%d", &n, &p);
for (int i = ; i <= n; i++)
{
m[i].end = NULL;
m[i].start = NULL;
m[i].sum = ;
}
for (int i = ; i<p; i++)
{
int op, s, v, t;
scanf("%d", &op);
if (op == )
{
scanf("%d%d", &s, &v);
if (m[s].sum == )
{
m[s].start = (node *)malloc(sizeof(node));
m[s].start->num = v;
m[s].start->q = NULL;
m[s].start->h = NULL;
m[s].end = NULL;
m[s].sum = ;
}
else
if (m[s].sum == )
{
m[s].end = (node *)malloc(sizeof(node));
m[s].end->num = v;
m[s].end->q = m[s].start;
m[s].end->h = NULL;
m[s].start->h = m[s].end;
m[s].sum = ;
}
else
{
node * z = (node *)malloc(sizeof(node));
z->num = v;
z->q = m[s].end;
z->h = NULL;
m[s].end->h = z;
m[s].end = z;
m[s].sum++;
}
}
else
if (op == )
{
scanf("%d", &s);
if (m[s].sum == )
printf("EMPTY\n");
else
{
m[s].sum--;
if (m[s].sum != )
printf("%d\n", m[s].end->num);
else
printf("%d\n", m[s].start->num);
if (m[s].sum != )
{
node *z = m[s].end->q;
z->h = NULL;
m[s].end = z;
}
else
{
m[s].end = NULL;
m[s].start = NULL;
}
}
}
else
{
scanf("%d%d", &s, &t);
if (m[s].sum == )
{
m[s].end = m[t].end;
m[s].start = m[t].start;
m[s].sum = m[t].sum;
m[t].sum = ;
m[t].end = NULL;
m[t].start = NULL;
}
else
if (m[s].sum == )
{
m[s].sum += m[t].sum;
m[t].sum = ;
if (m[t].start != NULL)
{
m[s].end = m[t].start;
m[s].start->h = m[t].start;
m[s].end->q = m[s].start;
if (m[t].end != NULL)
m[s].end = m[t].end;
else
m[s].end = m[t].start;
}
m[t].start = NULL;
m[t].end = NULL;
}
else
{
m[s].sum += m[t].sum;
m[t].sum = ;
if (m[t].start != NULL)
{
m[s].end->h = m[t].start;
m[t].start->q = m[s].end;
if (m[t].end != NULL)
m[s].end = m[t].end;
else
m[s].end = m[t].start;
}
m[t].start = NULL;
m[t].end = NULL;
}
}
}
}
//system("pause");
return ;
}
