CFR 228 E. The Road to Berland is Paved With Good Intentions ( 2SAT )

Problem - 228E - Codeforces

題意：
給 N 個點 M 條邊，邊有邊權 0 或 1。每次操作選取一個點，將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1，若有則輸出方案。

資料規模：
N ≤ 100

解法：
考慮每個邊，其實只能被兩端點控制，而任何一個點做兩次以上的操作沒有意義。因此可以列出布林關係式，若這個邊權為 0，端點為 u 和 v，那麼要有：

把它寫成：

邊權為 1 時也類似，就能用 2SAT 水過。

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

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

const int MAXN = 100;

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

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

void dfs_ksrj( int u, vector< int > &scc, vector< vector< int > > &scc_vec, int cnt ){
  for( int v : G[ u ] ){
    if( scc[ v ] ) continue;
    scc[ v ] = cnt;
    scc_vec[ cnt ].emplace_back( v );
    dfs_ksrj( v, scc, scc_vec, cnt );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ){
    int u, v, w; cin >> u >> v >> w; --u, --v;
    if( w == 1 ){
      G[ u ].emplace_back( v );
      G[ N + u ].emplace_back( N + v );
      G[ v ].emplace_back( u );
      G[ N + v ].emplace_back( N + u );
    } else{
      G[ u ].emplace_back( N + v );
      G[ N + u ].emplace_back( v );
      G[ v ].emplace_back( N + u );
      G[ N + v ].emplace_back( u );
    }
  }
  int scc_cnt = 0;
  vector< int > scc( 2 * N ), stk;
  vector< vector< int > > scc_vec( 1 );
  { // kosaraju
    vector< int > vis( 2 * N );
    for( int i = 0; i < 2 * N; ++i ){
      if( vis[ i ] ) continue;
      vis[ i ] = 1;
      dfs_topo( i, vis, stk );
    }
    for( int i = stk.size() - 1; i >= 0; --i ){
      if( scc[ stk[ i ] ] ) continue;
      scc[ stk[ i ] ] = ++scc_cnt;
      scc_vec.emplace_back( vector< int >() );
      scc_vec[ scc_cnt ].emplace_back( stk[ i ] );
      dfs_ksrj( stk[ i ], scc, scc_vec, scc_cnt );
    }
  }
  vector< int > sat( 2 * N );
  for( int i = 0; i < 2 * N; ++i ){
    if( sat[ i ] ) continue;
    if( scc[ i ] == scc[ i < N ? i + N : i - N ] ){
      cout << "Impossible\n";
      exit( 0 );
    }
    sat[ scc[ i ] ] = 1;
    sat[ scc[ ( i < N ? i + N : i - N ) ] ] = 2;
  }
  vector< int > ans;
  for( int i = 1; i <= scc_cnt; ++i ){
    if( sat[ i ] == 1 ) continue;
    for( int j = 0; j < scc_vec[ i ].size(); ++j ){
      if( N <= scc_vec[ i ][ j ] ) continue;
      ans.emplace_back( scc_vec[ i ][ j ] + 1 );
    }
  }
  cout << ans.size() << endl;
  for( int i = 0; i < ans.size(); ++i ){
    cout << ans[ i ] << " \n"[ i + 1 == ans.size() ];
  }
  return 0;
}