题目链接：https://vjudge.net/contest/219056#problem/A
推荐博客：https://blog.csdn.net/ck_boss/article/details/39429285
发现上面的这位大佬的思路和我一样，自己代码太多错误就参考了一下。
题意：
输入n，接下来会输入输入n个字符串，然后输入m，接下来会输入m对字符串，每一对表示左边的字符串可以变成右边的字符串，但是右边的不可以变成左边的。字符串不论大小写，现在要我们经过变换把一开始的n个字符里面的字符 ' r'或'R'（不分大小写，你全部改成大写或小写）最少，如果有多个r最少，那么就换成总长度最短的，输出r的个数和总长度。
额，网上大多数好像使用BFS写的，但是我写得时候因为在做图论的题，就强行联想到了tarjan算法，然后就不想换思路，就用tarjan加DFS写了，代码比较长而且比较难看，先说一下思路，有兴趣的可以看代码，虽然比较。。。
思路就是先tarjan缩点，把可以两两相互替换的字符串（在同一个强连通分量里面）缩点染色，同时记录这个强连通分量里面最小的r个数和对于最短的长度。之后把缩完的点二次建图，最后用DFS找答案。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100005
struct node{
int value,length;
}dot[maxn],min1[maxn];//dot数字记录每个字符串编号之后对应的值
//min1数组记录染色之后每个强连通分量里面最符合的值
struct EDGE{
int v,next;
}edge[maxn],edge2[maxn];//这里要两次建图，一次是给字符串编号之后建图，还有一次是缩点之后重新建图
int a[maxn];
int head[maxn],head2[maxn];
int dfn[maxn],low[maxn],color[maxn],s[maxn];
int n,m,k,t;
int cnt,time,ans,id,top,num,cnt2;
map<string,int>mp;//给每个字符串编号
map<pair<int,int>,int>mmp;//重新建图的时候防止重复的边
bool vis[maxn];
void init()
{
mmp.clear();
mp.clear();
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(head2,-,sizeof(head2));
cnt=time=ans=id=top=num=;
memset(vis,false,sizeof(vis));
cnt2=;
for(int i=;i<maxn;i++)
{
min1[i].length=min1[i].value=INF;
}
}
void cal(string &s)//编号并计算r的个数和字符串长度
{
mp[s]=++id;
int value=;
for(int i=;i<s.size();i++)
{
if(s[i]=='r')
value++;
}
dot[mp[s]].value=value;//dot记录字符串s对应编号的r个数和长度
dot[mp[s]].length=s.size();
}
void tarjan(int u)//缩点染色
{
dfn[u]=low[u]=++time;
s[top++]=u;
vis[u]=true;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],dfn[v]);
}
else if(vis[v])//必须要在栈内，因为这里不一定是一个连通图，所以一定要判断是否在栈内
//并且一定要写成dfn[v]，不能写成low[u]
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
ans++;
int v;
do{
v=s[--top];
vis[v]=false;
color[v]=ans;
if(dot[v].value<min1[ans].value||dot[v].value==min1[ans].value&&dot[v].length<min1[ans].length)
{
//min1数组记录每个强连通分量里面最优的结果
min1[ans].value=dot[v].value;
min1[ans].length=dot[v].length;
}
}while(v!=u);
}
}
void addedge(int u,int v)
{
edge[++cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void addedge2(int u,int v)
{
edge2[++cnt2].v=v;
edge2[cnt2].next=head2[u];
head2[u]=cnt2;
}
void get_edge2()
{
for(int i=;i<=id;i++)
{
for(int j=head[i];j!=-;j=edge[j].next)
{
int v=edge[j].v;
if(color[i]!=color[v]&&mmp[make_pair(color[i],color[v])]==)
{
addedge2(color[i],color[v]);
mmp[make_pair(color[i],color[v])]=;
}//两个强连通分量之间建一条有向图，可能有重复边,我们用mmp记录去掉
}
}
}
node bijiao(node s1,node s2)
{
if(s1.value<s2.value||s1.value==s2.value&&s1.length<s2.length)
return s1;
return s2;
}
void DFS(LL u)
{
if(vis[u])
return;
vis[u]=true;
for(int i=head2[u];i!=-;i=edge2[i].next)
{
int v=edge2[i].v;
if(!vis[v])
DFS(v);
min1[u]=bijiao(min1[u],min1[v]);
}
return;
}
string ope(string str)
{
for(int j=;j<str.size();j++)
{
if(str[j]>='A'&&str[j]<='Z')//全部变成小写
str[j]=str[j]-'A'+'a';
}
return str;
}
int main()
{
while(cin>>n)
{
init();
string str;
for(int i=;i<n;i++)
{
cin>>str;
str=ope(str);
if(mp[str]==)//编号
cal(str);
a[i]=mp[str];//记录文章里面字符串的编号
}
cin>>m;
string s1,s2;
for(int i=;i<m;i++)
{
cin>>s1>>s2;
s1=ope(s1);
s2=ope(s2);
if(mp[s1]==)
cal(s1);
if(mp[s2]==)
cal(s2);
addedge(mp[s1],mp[s2]);//建图，从s1的编号到s2的编号的有向边
}
for(int i=;i<=id;i++)//求强连通分量
{
if(!dfn[i])
tarjan(i);
}
get_edge2();//缩点之后重新建图
LL sum1=,sum2=;
int flag[maxn];
memset(vis,false,sizeof(vis));
memset(flag,,sizeof(flag));
//DFS(c);//试了无数次，不知道这句为什么放在这里就错了 ，不然可以节省很多时间
for(int i=;i<n;i++)
{
LL c=color[a[i]];
if(!flag[c])
{
memset(vis,,sizeof(vis));
DFS(c);//不知道为啥放在这里就对了
flag[c]=;
}
sum1+=min1[c].value;
sum2+=min1[c].length;
}
cout<<sum1<<' '<<sum2<<endl;
}
return ;
}