又写了一遍，tarjan真的容易写错……
如果没有x类型显然就是2SAT，如果有的话一个很自然的想法就是枚举它是A，B还是C. 但是注意到我们在做2SAT，只要把可能的情况限制在2种以内就可以了. 所以对于x类型的地图，可以枚举它不是A和它不是B两种情况（不需要枚举不是C，因为这肯定包含在前两种情况里面）.
错误的tarjan：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26void tarjan(ele i){
dfn[i]=low[i]=tcnt++;
instack[i]=true;
stk[top++]=i;
for (edge *j=h[i]; j; j=j->nxt)
if (!~dfn[j->v]){
tarjan(j->v);
low[i]=min(low[i],low[j->v]);
}
else if (instack[j->v]) low[i]=min(low[i],dfn[j->v]);
if (low[i]==dfn[i]){
bool r=true;
for (int j=top-1; ; --j){
if (ans[stk[j]] || ans[stk[j]^1]) r=r && ans[stk[j]];
if (stk[j]==i) break;
}
do{
ans[stk[top-1]]=r;
ans[stk[top-1]^1]=r^1;
blg[stk[top-1]]=bcnt;
--top;
}while (stk[top]!=i);
++bcnt;
}
instack[stk[top-1]]=false;
}
正确的tarjan：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26void tarjan(ele i){
dfn[i]=low[i]=tcnt++;
instack[i]=true;
stk[top++]=i;
for (edge *j=h[i]; j; j=j->nxt)
if (!~dfn[j->v]){
tarjan(j->v);
low[i]=min(low[i],low[j->v]);
}
else if (instack[j->v]) low[i]=min(low[i],dfn[j->v]);
if (low[i]==dfn[i]){
bool r=true;
for (int j=top-1; ; --j){
if (ans[stk[j]] || ans[stk[j]^1]) r=r && ans[stk[j]];
if (stk[j]==i) break;
}
do{
ans[stk[top-1]]=r;
ans[stk[top-1]^1]=r^1;
blg[stk[top-1]]=bcnt;
instack[stk[top-1]]=false;
--top;
}while (stk[top]!=i);
++bcnt;
}
}
tarjan一定要注意栈的问题，目前发现的易错点一个是忘了弹栈（写圆方树的时候，如果是一条树边，需要弹栈），一个是在错误的地方弹栈（在有向图的dfs树里会有横叉边，instack里面 不能 只保存当前点到根路径上的点，参考上面的代码）.
完整的AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
using namespace std;
struct rl{
ele i,hi,j,hj;
}a[maxn];
struct edge{
ele v;
edge *nxt;
}ep[maxm],*ecnt;
ele n,d,m,tcnt,bcnt,top,stk[maxn],b[maxn],dfn[maxn],low[maxn],blg[maxn];
char s[maxn];
bool flag,ans[maxn],instack[maxn];
edge *h[maxn];
inline void addedge(ele u,ele v){
edge *p=ecnt++;
p->v=v; p->nxt=h[u];
h[u]=p;
}
inline ele idx(ele i,ele j){
j=(j-b[i]+2)%3;
return i<<1|j;
}
void tarjan(ele i){
dfn[i]=low[i]=tcnt++;
instack[i]=true;
stk[top++]=i;
for (edge *j=h[i]; j; j=j->nxt)
if (!~dfn[j->v]){
tarjan(j->v);
low[i]=min(low[i],low[j->v]);
}
else if (instack[j->v]) low[i]=min(low[i],dfn[j->v]);
if (low[i]==dfn[i]){
bool r=true;
for (int j=top-1; ; --j){
if (ans[stk[j]] || ans[stk[j]^1]) r=r && ans[stk[j]];
if (stk[j]==i) break;
}
do{
ans[stk[top-1]]=r;
ans[stk[top-1]^1]=r^1;
blg[stk[top-1]]=bcnt;
instack[stk[top-1]]=false;
--top;
}while (stk[top]!=i);
++bcnt;
}
}
void dfs(ele i){
if (flag) return;
if (i==n){
ecnt=ep; memset(h,0,sizeof(h));
for (int j=0; j<m; ++j){
if (a[j].hi==b[a[j].i]) continue;
ele u=idx(a[j].i,a[j].hi);
if (a[j].hj==b[a[j].j]) addedge(u,u^1);
else{
ele v=idx(a[j].j,a[j].hj);
addedge(u,v);
addedge(v^1,u^1);
}
}
memset(dfn,-1,sizeof(dfn)); tcnt=bcnt=top=0;
memset(ans,0,sizeof(ans));
for (int j=0; j<(n<<1); ++j)
if (!~dfn[j]) tarjan(j);
for (int j=0; j<n; ++j)
if (blg[j<<1]==blg[j<<1|1]) return;
for (int j=0; j<n; ++j){
ele u=(b[j]+1+ans[j<<1|1])%3;
putchar('A'+u);
}
puts("");
flag=true;
return;
}
if (s[i]!='x'){
b[i]=s[i]-'a';
dfs(i+1);
}
else{
b[i]=0;
dfs(i+1);
if (flag) return;
b[i]=1;
dfs(i+1);
}
}
int main(){
scanf("%d%d%s%d",&n,&d,s,&m);
for (int i=0; i<m; ++i){
ele _a,c; char b[5],d[5];
scanf("%d%s%d%s",&_a,b,&c,d);
a[i]=(rl){_a-1,b[0]-'A',c-1,d[0]-'A'};
}
flag=false; memset(instack,0,sizeof(instack));
dfs(0);
if (!flag) puts("-1");
return 0;
}