1 文本格式
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxk = 5005;
int n, k;
int id[maxn][5];
char s[maxn][5][5], ans[maxk];
bool vis[maxn];
struct Edge {
int v, nxt;
} e[maxn * 100];
int head[maxn], tot = 1;
void addedge(int u, int v) {
e[tot].v = v;
e[tot].nxt = head[u];
head[u] = tot++;
}
int dfn[maxn], low[maxn], color[maxn], stk[maxn], ins[maxn], top, dfs_clock, c;
void tarjan(int x) { // tarjan算法求强联通
stk[++top] = x;
ins[x] = 1;
dfn[x] = low[x] = ++dfs_clock;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
} else if (ins[v])
low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x]) {
c++;
do {
color[stk[top]] = c;
ins[stk[top]] = 0;
} while (stk[top--] != x);
}
}
int main() {
scanf("%d %d", &k, &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) scanf("%d%s", &id[i][j], s[i][j]);
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
if (j == k) continue;
int u = 2 * id[i][j] - (s[i][j][0] == 'B');
int v = 2 * id[i][k] - (s[i][k][0] == 'R');
addedge(u, v);
}
}
}
for (int i = 1; i <= 2 * k; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= 2 * k; i += 2)
if (color[i] == color[i + 1]) {
puts("-1");
return 0;
}
for (int i = 1; i <= 2 * k; i += 2) {
int f1 = color[i], f2 = color[i + 1];
if (vis[f1]) {
ans[(i + 1) >> 1] = 'R';
continue;
}
if (vis[f2]) {
ans[(i + 1) >> 1] = 'B';
continue;
}
if (f1 < f2) {
vis[f1] = 1;
ans[(i + 1) >> 1] = 'R';
} else {
vis[f2] = 1;
ans[(i + 1) >> 1] = 'B';
}
}
ans[k + 1] = 0;
printf("%s\n", ans + 1);
return 0;
}
2 代码格式
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxk = 5005;int n, k;
int id[maxn][5];
char s[maxn][5][5], ans[maxk];
bool vis[maxn];struct Edge {int v, nxt;
} e[maxn * 100];int head[maxn], tot = 1;void addedge(int u, int v) {e[tot].v = v;e[tot].nxt = head[u];head[u] = tot++;
}int dfn[maxn], low[maxn], color[maxn], stk[maxn], ins[maxn], top, dfs_clock, c;void tarjan(int x) { // tarjan算法求强联通stk[++top] = x;ins[x] = 1;dfn[x] = low[x] = ++dfs_clock;for (int i = head[x]; i; i = e[i].nxt) {int v = e[i].v;if (!dfn[v]) {tarjan(v);low[x] = min(low[x], low[v]);} else if (ins[v])low[x] = min(low[x], dfn[v]);}if (dfn[x] == low[x]) {c++;do {color[stk[top]] = c;ins[stk[top]] = 0;} while (stk[top--] != x);}
}int main() {scanf("%d %d", &k, &n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= 3; j++) scanf("%d%s", &id[i][j], s[i][j]);for (int j = 1; j <= 3; j++) {for (int k = 1; k <= 3; k++) {if (j == k) continue;int u = 2 * id[i][j] - (s[i][j][0] == 'B');int v = 2 * id[i][k] - (s[i][k][0] == 'R');addedge(u, v);}}}for (int i = 1; i <= 2 * k; i++)if (!dfn[i]) tarjan(i);for (int i = 1; i <= 2 * k; i += 2)if (color[i] == color[i + 1]) {puts("-1");return 0;}for (int i = 1; i <= 2 * k; i += 2) {int f1 = color[i], f2 = color[i + 1];if (vis[f1]) {ans[(i + 1) >> 1] = 'R';continue;}if (vis[f2]) {ans[(i + 1) >> 1] = 'B';continue;}if (f1 < f2) {vis[f1] = 1;ans[(i + 1) >> 1] = 'R';} else {vis[f2] = 1;ans[(i + 1) >> 1] = 'B';}}ans[k + 1] = 0;printf("%s\n", ans + 1);return 0;
}