题目链接【https://nanti.jisuanke.com/t/27647】
//计蒜客2018复赛D题，想简单了。
题解：
题目是中文的，不再赘述。
题解：
分为三种情况：1、两个字符串都不能变：这种情况最简单，直接暴力判断两个支付穿是否相同即可。
2、两个字符串都能变：把上下对应位置不同的点连无向边（因为都可以改变），建立了一个深林，这里用并查集实现，顺便维护每个联块的大小，对于每个联通块来说，要把这些点都变成一样的，最少要变换（size-1）次，即选出一个点，把其他的点都变成被选中的点。
3、一个能变，一个不能变：这种情况最复杂。同第二种情况，这里需要建图，建立单向边，（只能由V变成C），对于每一个联通块，我们判断该联通块是不是DAG，如果是，那么只需要改变（size-1）次就行了。如果不是DAG,那么联通块中存在环，那么最少要变（size）次，只需要把这些点连接成有向环就可以了，保证了两两可以互达。
只是思路、具体细节和原因需要自己思考。欢迎斧正。QQ2421780543。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + ;
LL a[maxn], b[maxn];
char s[], t[];
//-----------------------并查集
int fa[maxn], val[maxn];
void init()
{
for(int i = ; i <= ; i++)
fa[i] = i, val[i] = ;
}
int Find(int u)
{
if(fa[u] == u)
return u;
return fa[u] = Find(fa[u]);
}
void Unit(int u, int v)
{
int x = Find(u);
int y = Find(v);
if(x != y)
{
fa[x] = y;
val[y] += val[x];
val[x] = ;
}
}
//-------------------------EDGE
int rd[maxn], vis[maxn], cnt = ;;
vector<int>vt[maxn];
map<int, int>mp;
queue<int>que;
struct Edge
{
int to, next;
Edge(int to = , int next = ): to(to), next(next) {}
} E[maxn * ];
int head[maxn], tot;
void Init_Edge()
{
for(int i = ; i <= ; i++)
head[i] = -;
tot = ;
}
void Add_Edge(int u, int v)
{
E[tot] = Edge(v, head[u]);
head[u] = tot++;
}
//--------------------------主函数
int main ()
{
int n, fg1 = , fg2 = ;
scanf("%d", &n); scanf("%s", s);
for(int i = ; i <= n; i++)
scanf("%lld", &a[i]);
scanf("%s", t);
for(int i = ; i <= n; i++)
scanf("%lld", &b[i]); if(s[] == 'V')
fg1 = ;
if(t[] == 'V')
fg2 = ; if((!fg1) && (!fg2))//都不能更改
{
bool ans = true;
for(int i = ; i <= n && ans; i++)
if(a[i] != b[i])
ans = false;
if(ans)
printf("0\n");
else
printf("-1\n");
}
else if(fg1 && fg2)//都可以更改
{
init();
for(int i = ; i <= n; i++)
{
if(a[i] != b[i])
Unit(a[i], b[i]);
}
int num = ;
for(int i = ; i <= ; i++)
{
Find(i);
if(fa[i] == i)
num += val[i] - ;
}
printf("%d\n", num); }
else //只能改一个
{
init();
Init_Edge();
for(int i = ; i <= n; i++)
if(a[i] != b[i])
{
Unit(a[i], b[i]);
Add_Edge(a[i], b[i]);
rd[b[i]] ++;
vis[a[i]] = vis[b[i]] = ;
}
for(int i = ; i <= ; i++)//提取联通块
{
if(vis[i])
{
int t = Find(i);
if(mp[t])
{
int tmp = mp[t];
vt[tmp].push_back(i);
}
else
{
mp[t] = ++cnt;
vt[cnt].push_back(i);
}
}
}
int num = ;
for(int i = ; i <= cnt; i++)//拓扑排序，判断DAG
{
int len = vt[i].size();
for(int j = ; j < len; j++)
{
int tmp = vt[i][j];
if(rd[tmp] == )
que.push(tmp);
}
int tmp = ;
while(!que.empty())
{
int u = que.front();
que.pop();
tmp++;
for(int j = head[u]; j != -; j = E[j].next)
{
int v = E[j].to;
rd[v]--;
if(rd[v] == )
que.push(v);
}
}
if(tmp == len)
num += len - ;
else
num += len;
}
printf("%d\n", num);
}
return ;
}