题目链接：https://hpuoj.com/contest/23/problem/I/

                                              I. Same String

单点时限: 2.0 sec

内存限制: 512 MB

有两个只由小写字母组成的长度为n的字符串s1,s2和m组字母对应关系，每一组关系由两个字母c1和c2组成，代表c1可以直接变成c2,你需要判断s1是否可以通过这m组关系转换为s2。

输入格式

第一行输入一个n(1≤n≤100)，代表字符串的长度。
第二行和第三行输入两个字符串s1,s2。
第四行输入一个m(1≤m≤325)，代表有m组关系。
接下来m行，第i行两个字符ui,vi,代表ui可以直接变为vi。

输出格式

如果s1可以通过这些m组关系转化变为s2，输出”YES”，否则输出”NO”。

分析：

把出现的字母当作点a能变成b就说明a到b有一条边

建图，注意是有向图。

然后遍历一遍，我没想到什么好的方法，用了floyd最短路算法，这样就能直接判断一个点是否可以到达另一个点。

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 30;

int G[N][N];
int dp[N][N];

void floyd()    // floyd最短路算法
{
    for(int k=0; k<N; k++)
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
}


int main()
{
    int n;
    char s1[107], s2[107];
    while(scanf("%d", &n) != EOF)
    {
        getchar();
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(i == j)  dp[i][j] = 0;
                else    dp[i][j] = INF;
            }
        }

        scanf("%s %s", s1, s2);
        // printf("s1 = %s  s2 = %s\n", s1, s2);
        int m;
        scanf("%d", &m);
        // printf("m = %d\n", m);
        getchar();
        for(int i=0; i<m; i++)
        {
            char u, v;
            scanf("%c %c", &u, &v);
            getchar();
            // printf("u = %c v = %c\n", u, v);
            dp[u-'a'][v-'a'] = 1;
        }
        floyd();
        int i;
        for(i=0; i<n; i++)
        {
            if(dp[s1[i] - 'a'][s2[i] - 'a'] != INF)
                continue;
            else
                break;
        }
        if(i == n)
            printf("YES\n");
        else
            printf("NO\n");
    }



    return 0;
}