题目描述

Description

你现在可能已经听说过 Rushmore 山上有一个壮观的石雕刻画了四位著名的美国总统。然而，很少有人知道这个纪念雕刻暗藏一个秘密的房间。这听起来像是一部好莱坞电影的情节，但是这个房间是真实存在的。它藏在 Abraham Lincoln 的头后面，它被设计成一个档案库，用来存放美国历史上重要的文件与文物。历史学家声称这个档案库的建造在 1939 年被中断，直到 20 世纪 90 年代末才能被访问，但这不是全部的真相。
在 1982 年，著名的考古学家 S. Dakota Jones 秘密地访问了这座纪念雕刻，发现房间已经完成建造，但不对外公开。这似乎有些可疑，经过一些开凿，她发现一个隐藏的地下室和一些文件。不幸的是，这些文件没什么有效信息，都是很无聊的内容。她猜测这些内容被加密了，但是她费尽心机还是无法解
密。
在这周的前些时候， Jones 博士在当地参加 ACM-ICPC 世界总决赛，她终于在 South DakotaSchool of Mines and Technology 的 Connolly Hall 发现了破译这些文件的密钥。她发现文件包含了一系列字母转换规则。一些字母可以经过多次转换，但一些字母没有转换规则。经过对那份无聊的文件中的单词多次转换之后，她似乎能把内容破译成美国历史上的文件，例如独立宣言和美国宪法。她需要你的帮助。
你将得到字母可能的转换规则和一系列原始单词与解密单词。你的任务是验证每对单词是否匹配。
如果两个单词具有相同的长度，且第一个单词的每个字母可以用转换规则多次转换后变成第二个单词中对应位置的字母，则两个单词匹配。

Input

第一行包含两个整数 m (1 ≤ m ≤ 500) 和 n (1 ≤ n ≤ 50) ，其中 m 表示字母转换规则的数量， n表示单词对的数量。
接下来 m 行，每行包含两个不同的字母 a 和 b ，表示字母 a 可以转换成字母 b 。每个有序对 (a, b)只会出现至多一次。
接下来 n 行，每行包含一对需要检查的单词。
转换规则和单词只会使用小写字母 ’a’ 到 ’z’ ，且每个单词包含至少 1 个字母，至多 50 个字母。

Output

对于每对单词，如果两个单词可以匹配，输出 yes ，否则输出 no 。

Sample Input

样例1
9 5
c t
i r
k p
o c
r o
t e
t f
u h
w p
we we
can the
work people
it of
out the
样例2
3 3
a c
b a
a b
aaa abc
abc aaa
acm bcm

Sample Output

样例1
yes
no
no
yes
yes
样例2
yes
no
yes

题目分析

直接floyd传递闭包 判断出26个字母之间是否互通 然后暴力check即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
char s[100],t[100];
int f[50][50];
void floyed()
{
    for(int k=1;k<=26;k++)
        for(int i=1;i<=26;i++)
            for(int j=1;j<=26;j++)
                if(f[i][k]&&f[k][j]) f[i][j]=1;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%s%s",&s[0],&t[0]);
        f[(s[0]-'a')+1][(t[0]-'a')+1]=1;
    }
    floyed();
    for(int i=1;i<=n;i++)
    {
        scanf("%s%s",&s[0],&t[0]);
        int lens=strlen(s),lent=strlen(t);
        if(lens!=lent) printf("no\n");
        else
        {   
            int flag=0;
            for(int j=0;j<lens;j++)
                if(s[j]!=t[j]&&!f[(s[j]-'a')+1][(t[j]-'a')+1])
                {
                    printf("no\n");
                    flag=1;
                    break;
                }
            if(!flag) printf("yes\n");
        }
    }
    return 0;
}