2-sat问题及求解方案: tarjan算法 加 dfs 搜索方案 :
//cin.tie(0),cout.tie(0); 进一步加快执行效率. 不能和scanf与printf连用.
//cout << fixed << setprecision() << ;
//floor();向下取整
//ceil();向上取整
//rand();随机数
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll; // -9223372036854775807ll - 1 ~ 9223372036854775807ll 9e+18
//typedef unsigned long long ull;
//typedef unsigned int uint;
#define int long long
#define INF 0X7FFFFFFF
#define MAXN 1000005
#define nullptr 0
#define debug(x) cout<<#x<<" : "<<x<<endl
#define Enter(i,n) (i==n) ? cout<<endl : cout<<" "
#define loop(i,x,n) for( int i = x ; i <= n ; ++i )
#define loop_(i,x,n) for( int i = x ; i >= n ; --i )
#define input(x) scanf("%lld",&x)
#define output(x) printf("%lld",x)
#define new_line printf("\n")
#define blank printf(" ")
const int MAX=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int Max=998244353;
const double eps=1e-8;
void init();
void solve();
int ***(int a,int b);
inline int read();
inline void write(int x);
int min(int x,int y){if(x<=y)return x;return y;}
int max(int x,int y){if(x>=y)return x;return y;}
//int Go[4][2]={ {1,0},{0,1},{-1,0},{0,-1} };
int QuickPow( int x , int pow )
{
int res = 1 ;
// x %= Max ;
// pow %= Max ;
while( pow ){
if( pow & 1 ) res = ( res * x ) ;
x = ( x * x ) ;
pow >>= 1 ;
}
return re***ool Is_prime(int x)
{
if( x == 0 || x == 1 ) return false ;
if( x == 2) return true ;
for( int i = 2 ; i*i <= x ; i++ ){
if( x%i == 0 ) return false ;
}
return true ;
}
#define often 2005
// ------------------------------------------------------------
vector< int > G[often] ;
vector< int > RG[often] ;
// vector< int > v ;
stack< int > st ;
int dfn[often] ;
int low[often] ;
bool vis[often] ;
int sccon[often] ;
int idex ;
int num ;
char ans[1005] ;
void tarjan( int x )
{
dfn[x] = low[x] = ++idex ;
vis[x] = 1 ;
st.push(x) ;
loop( i , 0 , (int)G[x].size()-1 ){
int y = G[x][i] ;
if( !dfn[y] ){
tarjan(y) ;
low[x] = min( low[x] , low[y] ) ;
}
else if( vis[y] ){
low[x] = min( low[x] , dfn[y] ) ;
}
}
if( dfn[x] == low[x] ){
num++ ;
while( !st.empty() ){
int z = st.top() ;
st.pop() ;
sccon[z] = num ;
vis[z] = 0 ;
if( z == x ) break ;
}
}
return ;
}
bool used[often] ;
void dfs( int x )
{
used[x] = 1 ;
loop( i , 0 , (int)G[x].size()-1 ){
if( !used[ G[x][i] ] ) dfs( G[x][i] ) ;
}
return ;
}
bool check( int x , int n )
{
memset( used , 0 , sizeof used ) ;
dfs( x ) ;
loop( i , 1 , n ){
if( used[i] && used[i+n] ) return 0 ;
}
return 1 ;
}
void solve()
{
int n , m ;
cin >> n >> m ;
int a , b ;
char c , h ;
loop( i , 1 , m ){
cin >> a >> c ;
cin >> b >> h ;
int x = ( c == 'N' ) ;
int y = ( h == 'N' ) ;
G[ (1-x)*n + a ].push_back( y*n + b ) ;
G[ (1-y)*n + b ].push_back( x*n + a ) ;
}
loop( i , 1 , 2*n ){
if( !dfn[i] ) tarjan( i ) ;
}
loop( i , 1 , n ){
if( sccon[i] == sccon[i+n] ){
puts("IMPOSSIBLE") ;
return ;
}
}
loop( i , 1 , n ){
bool x = check( i , n ) ;
bool y = check( i+n, n ) ;
if( x && y ) putchar('?') ;
else if( !x && y ) putchar('N') ;
else if( x && !y ) putchar('Y') ;
}
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
// clock_t start,last;
// start = clock();
init() ;
int _ = 1 ;
// input( _ ) ;
// cin >> _ ;
while( _-- ){
// srand( (int)time(0) ) ;
solve() ;
}
// system("pause");
// last = clock();
// cout<<(double)(last-start)/CLOCKS_PER_SEC;
// printf("%lf\n",(double)(last-start)/CLOCKS_PER_SEC ) ;
return 0;
}
void init()
{
return ;
}
int ***(int a,int b)
{
if(b)return ***(b,a%b);
return a;
}
// inline int read()
// {
// register int x = 0, t = 1;
// register char ch=getchar(); // 读入单个字符到寄存器
// while(ch<'0'||ch>'9'){
// if(ch=='-')t=-1;
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48); // 移位与异或
// // 第十行可以换成 x = x * 10 + ch - '0'
// ch=getchar();
// }
// return x*t;
// }
// inline void write(int x)
// {
// if(x<0){
// putchar('-');
// x=-x;
// }
// if(x>9) write(x/10);
// putchar(x%10+'0');
// }