题意给出多对映射关系 (1~50)多重映射 //注意映射关系有方向,且可以间接映射
思路:就是给出每个字母对应的映射关系,我们可以想到用邻接表来存储,在连接完之后在进行一次关联(由于有些映射关系属于间接关系第一次存图没有存完整)
这里直接开邻接矩阵来存,因为所需空间不大
完整题解:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char a[505],b[505]; int trans[30][30]; int main() { int n,m; while(cin>>n>>m) { char x,y; memset(trans,0,sizeof(trans)); for(int i=1; i<=n; i++) { cin>>x>>y; trans[x-'a'][y-'a']=1; } //间接关联 for(int i=0; i<26; i++) { for(int j=0; j<26; j++) { if(trans[i][j]==1) { for(int k=0; k<26; k++) { //所有关联i的也关联j if(trans[k][i]==1) trans[k][j]=1; } } } } for(int p=1; p<=m; p++) { scanf("%s %s",a,b); int lena=strlen(a); int lenb=strlen(b); int i=0,j=0,flag=0; while(i<lena&&j<lenb&&i==j&&flag==0) { if(a[i]==b[j]||trans[a[i]-'a'][b[j]-'a']==1) { i++; j++; } else flag=1; } if(lena==lenb&&flag==0) cout<<"yes"<<endl; else//长度不等直接判no cout<<"no"<<endl; } } return 0; }