萬球同心移位(C++參考)

// 測試資料改為第1行為 t 組，0<t<9，接著每組 第1列n  m ，接著 m列

/*  有n個球編號0~n-1{ 3<n<5*10^5}，先將n個球依順時鐘圍成一圈

m個指令F A B 或R A B {2<m<10^3}

F A B 代表將編號A的球移至B球的順鄰處 、 R A B 代表將編號A的球移至B球的逆鄰處

執行m個指令後，輸出編號0的 逆鄰 及 順鄰 */

參考程式：

#include <iostream>
using namespace std;
const int MaxN = 500000;
const int MaxM = 1000;
int r[MaxN];  //逆鏈
int f[MaxN];  //順鏈
void shout(int a)
{
// 將 a 號 ball 移出
r[ f[a] ]  =  r[a];
f[ r[a] ]  =  f[a];
}
void shinf(int a, int b)
{
//將 a 移入 b之順向鄰 
r[a] = b;
f[a] = f[b];
r[ f[b] ]  =  a;
f[b] = a;
}
void shinr(int a, int b)
{
//將 a 移入 b之逆向鄰 
f[a] = b;
r[a] = r[b];
f[ r[b] ]  =  a;
r[b] = a;
}
void print(int n) //印出逆、順 鏈結表
{
for(int i=0; i<n; ++i)
 cout <<i<<':' << r[i] <<' ' << f[i] << endl;
}
int main(void)
{
  int i,j,k , n,m,t;
  char c;  // 指令
  int a,b; // 將 a 球移至 b 鄰

  cin >> t;  // 資料組數 t
  while( t-- )
  {
     cin >> n >> m;
     // init r[] 及 f[]
     for(i=1; i<n-1; ++i)
     {
f[i]=i+1;
r[i]=i-1;
     }
    f[0] = 1; f[n-1] = 0;
    r[0] = n-1; r[n-1] = n-2;
     // 讀 m 個指令
    for(j=0; j<m; ++j)
    {
      cin >> c >> a >> b;
      if( (a==b) || (c=='F' && f[b]==a) || (c=='R' && r[b]==a) ) continue;
      shout( a ); //將 a 移出
      if(c=='F') shinf( a, b);  //將 a 移入 b之順向鄰 
      else shinr( a, b );  //將 a 移入 b之逆向鄰 
      cout << c << a<<','<<b<<endl;
      print(n);  // 測試用印鏈結
    }
    cout << r[0] <<' ' << f[0] << endl;
  }
 return 0;
}
/*  輸入
3
4 3
R 3 2
F 3 0
F 1 2
5 6
F 2 1
R 1 3
F 2 4
F 1 4
R 0 2
R 3 4
6 8
F 1 3
R 3 4
F 5 1
F 3 3
R 2 0
R 0 3
F 4 5
R 2 1
----- 輸出
1 3
1 2
4 3

*/