CFR 742 E. Arpa’s overnight party and Mehrdad’s silent entering ( Bicoloring / Random )

題意：
在一個圓桌上吃飯，有兩種飯，希望每連續三個人，都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶，而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配，輸出 -1。

資料規模：
情侶對數 1 ≤ n ≤ 1e5
時限 1000 ms
記憶體 256 MB

解法：
需要一點創意，考慮對兩兩相鄰的人進行唯一配對並連無向邊。情侶之間也連無向邊。會發現，若形成環，一定是偶環，因為那種切過來呈現的邊，對任何節點至多只有一個。進一步考慮，沒有奇環就代表一定可以二塗色，而二塗色後的結果正是所求。
另外可以隨機過，首先對每個情侶分配好不一樣的飯。接著不斷判斷是否完成，若遇到三個人都是同一個飯，假設是往右考慮，那就隨機選中間或右邊那個人和他的情侶互調飯。如果不隨機就會有無限循環的問題，可以想想看。不過，嚴謹的複雜度證明就完全想不到了，如果有人知道，請務必告訴我。

時間 / 空間複雜度：
O( N )

二塗色：

int N;
vi A, B;

void init(){
  cin >> N;
  A = B = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> A[ i ] >> B[ i ], --A[ i ], --B[ i ];
}

vvi G;
vi col;

void dfs( int u ){
  for( int v : G[ u ] )
    if( not col[ v ] )
      col[ v ] = 3 - col[ u ],
      dfs( v );
}

void preprocess(){
  G = vvi( 2 * N );
  for( int i = 0; i < N; ++i )
    G[ A[ i ] ].emplace_back( B[ i ] ),
    G[ B[ i ] ].emplace_back( A[ i ] ),
    G[ 2 * i ].emplace_back( 2 * i + 1 ),
    G[ 2 * i + 1 ].emplace_back( 2 * i );
  col = vi( 2 * N );
  for( int i = 0; i < 2 * N; ++i )
    if( not col[ i ] )
      col[ i ] = 1,
      dfs( i );
}

void solve(){
  for( int i = 0; i < N; ++i )
    cout << col[ A[ i ] ] << " " << col[ B[ i ] ] << endl;
}

隨機算法：

int N;
vi A, B;

void init(){
  cin >> N;
  A = B = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> A[ i ] >> B[ i ], --A[ i ], --B[ i ];
}

vi partner;
vi ans;

void preprocess(){
  partner = vi( N * 2 );
  ans = vi( N * 2 );
  for( int i = 0; i < N; ++i )
    partner[ A[ i ] ] = B[ i ],
    partner[ B[ i ] ] = A[ i ],
    ans[ A[ i ] ] = 1, ans[ B[ i ] ] = 2;
  while( true ){
    int modify = 0;
    for( int i = 0; i < 2 * N; ++i ){
      if( ans[ ( i - 1 + 2 * N ) % ( 2 * N ) ] == ans[ i ] and ans[ i ] == ans[ ( i + 1 ) % ( 2 * N ) ] ){
        if( rand() & 1 )
          swap( ans[ i ], ans[ partner[ i ] ] );
        else
          swap( ans[ ( i + 1 ) % ( 2 * N ) ], ans[ partner[ ( i + 1 ) % ( 2 * N ) ] ] );  
        modify = 1;
      }
    }
    if( not modify )
      break;
  }
}

void solve(){
  for( int i = 0; i < N; ++i )
    cout << ans[ A[ i ] ] << " " << ans[ B[ i ] ] << endl;
}