Problem
Solution
设\(p_{i,R/B}\)为第\(i\)号节点染成R或B所代表的点。考虑2-SAT，对于每一个猜的操作，其中任意一个与猜的答案颜色不同，则其他两个必须相同。我们暴力进行联边。然后Tarjan跑SCC最后构造输出即可。-1的情况即为存在\(p_{i,R}\)和\(p_{i,B}\)在同一个SCC中。
复杂度分析：每一个猜的操作会产生\(6\)条边，即总边数为\(6n\)，总点数为\(2k\)，复杂度为\(O(k + n)\)。
# include <bits/stdc++.h>
# define R 0
# define B 1
using namespace std;
const int N = 5005;
int k,n;
int p[N][2];
int id[4],col[4];
vector <int> g[N << 1];
int dfn[N << 1],low[N << 1],dfntot = 0,cnt = 0,belong[N << 1],s[N << 1],top = 0;
bool inq[N << 1];
void tarjan(int x,int fa)
{
dfn[x] = low[x] = ++dfntot,s[++top] = x,inq[x] = 1;
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
if(!dfn[v]) {tarjan(v,x); low[x] = min(low[x],low[v]);}
else if(inq[v]) low[x] = min(low[x],dfn[v]);
}
if(dfn[x] == low[x])
{
int v; ++cnt;
do
{
inq[v = s[top--]] = 0,belong[v] = cnt;
}while(top && v != x);
}
return;
}
int main(void)
{
scanf("%d%d",&k,&n);
for(int i = 1; i <= k; i++)
{
p[i][R] = (i << 1) - 1,p[i][B] = (i << 1);
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 3; j++)
{
int x; char ch;
scanf("%d %c",&x,&ch);
id[j] = x,col[j] = (ch == 'R') ? R : B;
}
for(int j = 1; j <= 3; j++)
{
for(int k = 1; k <= 3; k++)
{
if(j == k) continue;
g[p[id[j]][!col[j]]].push_back(p[id[k]][col[k]]);
}
}
}
for(int i = 1; i <= (k << 1); i++)
{
if(!dfn[i]) {top = 0; tarjan(i,0);}
}
for(int i = 1; i <= k; i++)
{
if(belong[p[i][R]] == belong[p[i][B]])
{
printf("-1\n");
return 0;
}
}
for(int i = 1; i <= k; i++)
{
if(belong[p[i][R]] < belong[p[i][B]])
{
printf("R");
}
else printf("B");
}
return 0;
}