CFR 781 B. Innokenty and a Football League ( 2SAT )

Problem - B - Codeforces

題意：
給 N 個姓名，現在要為每個姓名做縮寫，但希望滿足以下規則：
1. 姓名是 A 的前三個字元，或 A 的前兩個字元接上 B 的第一個字元。
2. 任何縮寫不重複
3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的，那麼 i 和 j 都不可以採取第一種縮寫。
問是否有合法的方案，有的話輸出。

資料規模：
N ≤ 1000

解法：
一看就覺得很 2SAT，雖然說看了大部份的人的做法都是貪心。
首先一個人要嘛採取第一種縮寫，要嘛採取第二種縮寫，有真/偽的性質。
再來可以討論兩個人衝突的情況進行建邊，u 指向 v 代表若 u 成立則 v 必須成立：
1. 若 i1 和 j1 衝突：
那麼就當作「就算選 i1，也硬是把你變成 i2」：
i1 -> i2
2. 若 i1 和 j2 衝突：
i1 -> j1
3. 若 i2 和 j1 衝突：
i2 -> j2
4. 若 i2 和 j2 衝突：
i2 -> j1
建完邊之後，做一次強連通分量分解。若存在任一對 ( i1, i2 ) 存在於同一個強連通分量，那麼無解，因為同一個強連通分量裡的所有布林值都必須一致。接著要按照拓撲序給各個強連通分量賦植，每次盡量給靠後面的「真」，原因是我們使用的第一種邊。

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

int N;
string A[ MAXN ], B[ MAXN ];

vector< int > G[ MAXN * 2 ], rG[ MAXN * 2 ];

void dfs_topo( int u, vector< int > &stk, vector< int > &vis ){
  for( int v : G[ u ] ){
    if( vis[ v ] ) continue;
    vis[ v ] = 1;
    dfs_topo( v, stk, vis );
  }
  stk.emplace_back( u );
}

void dfs_ksrj( int u, vector< int > &scc, const int scc_cnt ){
  for( int v : rG[ u ] ){
    if( scc[ v ] ) continue;
    scc[ v ] = scc_cnt;
    dfs_ksrj( v, scc, scc_cnt );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N;
    for( int i = 0; i < N; ++i ){
      cin >> A[ i ] >> B[ i ];
    }
  }
  {
    for( int i = 0; i < N; ++i ){
      for( int j = 0; j < N; ++j ){
        if( i == j ) continue;
        if( A[ i ].substr( 0, 3 ) == A[ j ].substr( 0, 3 ) ){
          G[ i ].emplace_back( N + i );
          rG[ N + i ].emplace_back( i );
        }
        if( A[ i ].substr( 0, 3 ) == A[ j ].substr( 0, 2 ) + B[ j ].substr( 0, 1 ) ){
          G[ i ].emplace_back( j );
          rG[ j ].emplace_back( i );
        }
        if( A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) == A[ j ].substr( 0, 3 ) ){
          G[ N + i ].emplace_back( N + j );
          rG[ N + j ].emplace_back( N + i );
        }
        if( A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) == A[ j ].substr( 0, 2 ) + B[ j ].substr( 0, 1 ) ){
          G[ N + i ].emplace_back( j );
          rG[ j ].emplace_back( N + i );
        }
      }
    }
  }
  {
    vector< int > stk, vis( 2 * N );
    for( int i = 0; i < 2 * N; ++i ){
      if( vis[ i ] ) continue;
      dfs_topo( i, stk, vis );
    }
    int scc_cnt = 0;
    vector< int > scc( 2 * N );
    for( int i = 2 * N - 1; i >= 0; --i ){
      if( scc[ stk[ i ] ] ) continue;
      scc[ stk[ i ] ] = ++scc_cnt;
      dfs_ksrj( stk[ i ], scc, scc_cnt );
    }
    for( int i = 0; i < N; ++i ){
      if( scc[ i ] == scc[ i + N ] ){
        cout << "NO\n";
        exit( 0 );
      }
    }
    vector< int > sat( scc_cnt + 1 );
    for( int i = 2 * N - 1; i >= 0; --i ){
      int x = scc[ stk[ i ] ];
      int y = scc[ stk[ i ] < N ? stk[ i ] + N : stk[ i ] - N ];
      if( sat[ x ] ) continue;
      if( sat[ y ] ){
        sat[ x ] = 3 - sat[ y ];
      } else{
        sat[ x ] = 2;
        sat[ y ] = 1;
      }
    }
    cout << "YES\n";
    for( int i = 0; i < N; ++i ){
      if( sat[ scc[ i ] ] == 1 ){
        cout << A[ i ].substr( 0, 3 ) << "\n";
      } else{
        cout << A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) << "\n";
      }
    }
  }
  return 0;
}