贝壳找房在遥远的传奇*，找到了一个强大的魔法师顾问。他有 22 串数量相同的法力水晶，每个法力水晶可能有不同的颜色。为了方便起见，可以将每串法力水晶视为一个长度不大于 10^5105，字符集不大于 10^5105 的字符串。现在魔法师想要通过一系列魔法使得这两个字符串相同。每种魔法形如 (u,\ v),\ u,\ v \le 10^5(u, v), u, v≤105，可以将一个字符 uu改成一个字符 vv，并且可以使用无限次。出于种种原因，魔法师会强行指定这两个串能否进行修改。
若失败输出 -1−1，否则输出最少使用的魔法的种类数。
输入格式
一个正整数 n(n \le 10^5)n(n≤105) 表示每个字符串的长度。
接下来两行每行首先输入一个单词（"Variable"或"Constant"），"Variable"表示这个字符串能进行修改，"Constant"表示这个字符串不能进行修改，然后 nn 个正整数表示一个字符集不大于 10^5105 的字符串。
输出格式
若有解，输出一个自然数表示最少使用的魔法的种类数。否则输出 -1−1。
保证所有输入的数字都为正整数且不大于 10^5105。
样例输入1
2
Constant 111 222
Variable 222 111
样例输出1
2
样例输入2
2
Variable 111 222
Variable 222 111
样例输出2
1
题目来源
不说了 SB错误能卡我好久。
对于cc的情况判字符串是不是相等。
对于vv的情况并查集找联通块数，次数就是总点数减去联通块数。
对于cv的情况我们仍旧双向存联通块。对于内部有自环的我们建的边数等于块内点数。对于没有自环的，我们建的边数等于块内点数-1。
第二种情况跟vv的是类似的，第一种情况则是把所有点建成一个大的自环，这样所有点都互相可达了。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define mod 1000000007
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=1e5+;
const int P=1e5;
int inf[];
int s[][N];
vector<int> e[N];
bool vis[N],ins[N];
bool ct[N];
int fa[N];
bool exist[N];
int now,ans;
char is[];
bool dfs(int u)
{
ins[u]=;
vis[u]=;
int flag=;
for(auto p:e[u])
{
if(ins[p])
{
flag=;
continue;
}
if(vis[p])
continue;
if(dfs(p)) flag=;
}
ins[u]=;
return flag;
}
int Find(int x) {return fa[x]==x?x: fa[x]=Find(fa[x]);}
void Union(int u,int v)
{
int x=Find(u),y=Find(v);
if(x!=y)
fa[x]=y;
return ;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<;i++)
{
scanf("%s",is);
if(strcmp(is,"Constant")==)
inf[i]=;
else
inf[i]=;
for(int j=;j<=n;j++)
scanf("%d",&s[i][j]);
}
if(inf[]==)
now=;
else
now=;
int pt=inf[]+inf[];
for(int i=;i<=P;i++)
fa[i]=i;
for(int i=;i<=n;i++)
{
if(pt>= && s[now][i]!=s[now^][i])
e[s[now][i]].pb(s[now^][i]),Union(s[now][i],s[now^][i]);
exist[s[now][i]]=;
exist[s[now^][i]]=;
}
ans=;
for(int i=;i<=P;i++)
{
if(e[i].size()>)
{
sort(e[i].begin(),e[i].end());
e[i].resize(unique(e[i].begin(),e[i].end())-e[i].begin());
}
if(exist[i]) ans++;
}
if(pt==)
{
bool flag=;
for(int i=;i<=n;i++)
if(s[][i]!=s[][i])
flag=;
if(flag)
printf("-1\n");
else
printf("0\n");
}
if(pt==)
{
for(int i=;i<=P;i++)
if(exist[i] && !vis[i])
if(dfs(i)) ct[Find(i)]=;
for(int i=;i<=P;i++)
if(exist[i] && fa[i]==i && ct[i]==)
ans--;
printf("%d\n",ans);
}
if(pt==)
{
for(int i=;i<=P;i++)
if(exist[i] && fa[i]==i)
ans--;
printf("%d\n",ans);
}
return ;
}