题解 | #[USACO 2011 Jan G]The Continental Cowngress#

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');
// }