链接：
题意：
给出 \(n(1\leq n\leq 1000)\) 个点，\(m(1\leq m\leq 4000)\) 个形如：“点 \(a\) 取 \(ca\) 或 点 \(b\) 取 \(cb\)，其中 \(ca,cb\in\{'Y','N'\}\)” 的限制。如果没有一组方案满足所有限制，输出"IMPOSSIBLE"；否则，可能有多组满足限制的解。对于一个点，如果在所有方案中都取 \('Y'\) 则该点最终答案为 \('Y'\)，如果在所有方案中都取 \('N'\) 则该点最终答案为 \('N'\)，如果都能取到，则该点最终答案为 \('?'\) ，输出最终 \(n\) 个点的答案。
分析：
我们知道，如果只需要一组答案，那么这就是 2-sat 的模板，但是该题似乎需要求出所有方案？
于是我们回顾使用 tarjan 算法求强连通分量解决 2-set 问题中最后取值的部分。
我们知道一个点的 true 和 false 我们会选择拓扑序较大的，这是因为拓扑序较小的可能会连向拓扑序较大的，而此时我们只能选择拓扑序较大的，不然会出现错误。我们发现这就是某个点必须选择某种取值的情况，即上文"在所有方案中都取XXX"，而相对应的，如果无法从拓扑序较小的连向较大的，就说明这两种取值都能取，也就是上文“如果都能取到”的情况了。所以我们的算法思路也就比较清晰了。
算法：
在正常 2-sat 建图，tarjan 求强连通分量后，如果无解，输出"IMPOSSIBLE"，否则对强连通分量建图，使用 bfs 判断每个点的两种取值的连通性即可。此时，tarjan 时间复杂度 \(O(n+m)\)，bfs \(O(n^2)\) ，将 \(n,m\) 视为同级别，则时间复杂度为 \(O(n^2)\)，可以通过此题。
代码：
#include<bits/stdc++.h>
using namespace std;
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=2e3+5;
const int M=8e3+5;
struct edge{
int v,next;
}e[M];
int head[N],en;
void insert(int u,int v){
e[++en].v=v;
e[en].next=head[u];
head[u]=en;
}
int n,m;
int sta[N],low[N],dfn[N],id[N],sum,sign,top;
bool vis[N];
void dfs(int u){
low[u]=dfn[u]=++sign;
vis[u]=true;sta[++top]=u;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
sum++;int i=sta[top--];
while(i!=u){
vis[i]=false;
id[i]=sum;
i=sta[top--];
}
vis[i]=false;
id[i]=sum;
}
}
bool check(){
for(int i=1;i<=n;i++)
if(id[i]==id[i+n])
return false;
return true;
}
struct llmmkk{
int v,next;
}f[M];
int h[N],fn;
void ins(int u,int v){
f[++fn].v=v;
f[fn].next=h[u];
h[u]=fn;
}
bool p[N][N];
int inq[N];
queue<int>q;
void bfs(int s){
memset(inq,0,sizeof(inq));
q.push(s);inq[s]=1;
while(!q.empty()){
int u=q.front();q.pop();p[s][u]=true;
for(int i=h[u];i;i=f[i].next){
int v=f[i].v;
if(!inq[v]) q.push(v);
}
}
}
signed main(){
n=in,m=in;
for(int i=1;i<=m;i++){
int a,b;char ta,tb;
cin>>a>>ta>>b>>tb;
insert(a+(ta=='N')*n,b+(tb=='Y')*n);
insert(b+(tb=='N')*n,a+(ta=='Y')*n);
}
for(int i=1;i<=n<<1;i++)if(!dfn[i])dfs(i);
if(check()){
for(int i=1;i<=n<<1;i++){
for(int j=head[i];j;j=e[j].next){
int v=e[j].v;
if(id[i]!=id[v])ins(id[i],id[v]);
}
}
for(int i=1;i<=n;i++){
int a=id[i],b=id[i+n];
if(!vis[a])bfs(a),vis[a]=1;
if(!vis[b])bfs(b),vis[b]=1;
if(p[a][b]) cout<<'Y';
else if(p[b][a]) cout<<'N';
else cout<<'?';
}
}
else cout<<"IMPOSSIBLE"<<'\n';
return 0;
}
题外话：
一遍过，需要对 2-sat 算法深刻理解，好题！