先看图代码会更容易理解
#include<stdio.h>
/*
测试数据:
6 2
A 1 4
B 3 5
输出样例:
2 1 4 5 3 6
*/
void Link(int x, int y, int right[], int left[])
{
right[x] = y;
left[y] = x;
}
int A[50000];
int left[50000], right[50000];
int main()
{
int i, m, n, x, y, t;
char type[2];
scanf("%d%d", &n, &m);
for (i = 0; i <= n; i++)
{
A[i] = i;
}
for (i = 0; i <= n; i++)//初始化数组right
{
if (i != n)
{
right[i] = i + 1;
}
else
{
right[i] = 0;
}
}
for (i = 1; i <= n + 1; i++)//初始化数组left
{
left[i] = i - 1;
}
for (i = 0; i < m; i++)
{
scanf("%s%d%d", type, &x, &y);
Link(left[x], right[x], right, left);
if (type[0] == 'A')
{
Link(left[y], x, right, left);
Link(x, y, right, left);
}
else
{
Link(x, right[y], right, left);
Link(y, x, right, left);
}
}
t = 1;
while (t != 0)
{
printf("%d ", A[t]);
t = right[t];
}
return 0;
}