【题解】慈溪中学-8.14-T2

传送门
貌似是一种叫$2-SAT$的东西
我理解是一种建图思想
分两层考虑
选一个对的就要选两个错的，这样来建图
然后缩点
若一个点对应在两层的被缩在同一点，矛盾，输出-1
否则正常输出
Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], Index, dfn[maxn], low[maxn], vis[maxn], top, sta[maxn], n, m, tot, color[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

inline int get(){
	char c = getchar();
	for (; c != 'R' && c != 'B'; c = getchar());
	return c == 'B';
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void tarjan(int u){
	dfn[u] = low[u] = ++Index;
	vis[u] = 1, sta[++top] = u;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else
		if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		++tot;
		while (sta[top + 1] != u) vis[sta[top]] = 0, color[sta[top--]] = tot;
	}
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int p1 = read(), q1 = get(),
			p2 = read(), q2 = get(),
			p3 = read(), q3 = get();
		addedge(p1 + q1 * n, p2 + (q2 ^ 1) * n);
		addedge(p1 + q1 * n, p3 + (q3 ^ 1) * n);
		addedge(p2 + q2 * n, p1 + (q1 ^ 1) * n);
		addedge(p2 + q2 * n, p3 + (q3 ^ 1) * n);
		addedge(p3 + q3 * n, p1 + (q1 ^ 1) * n);
		addedge(p3 + q3 * n, p2 + (q2 ^ 1) * n);
	}
	for (int i = 1; i <= (n << 1); ++i) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; ++i)
		if (color[i] == color[i + n]) return puts("-1"), 0;
	for (int i = 1; i <= n; ++i)
		printf(color[i] < color[i + n] ? "R" : "B");
	return 0;
}