题目链接：Codeforces/Vjudge

题目大意：在object oriented programming 语言中的类之间存在两种关系 is-a，has-a，分别为子类与包含关系。给出若干初始条件，然后进行若干询问（A是否是B的子类或A是否包含B）， 请回答询问是否真。

is-a关系具有传递性，所以可以通过解传递闭包的方法来做这个题目。如果从A到C存在一条全部由is-a关系构成的道路， 那么A is-a C。如果连接AC的道路中间存在某个has-a关系，则从这个has-a关系之后的所有关系都应该变为has-a。

需要注意的坑就是两个类之间也许不只有一种关系，所以is和has需要分开。

Floyd算法的AC代码：

#include <iostream>
#include <string>
#include <map>

using namespace std;
const int MAXN = (int) 5e2 + 5;
bool is[MAXN][MAXN];
bool has[MAXN][MAXN];
bool rel[MAXN][MAXN][2];

inline void init() {
    fill(&is[0][0], &is[0][0] + MAXN * MAXN, false);
    fill(&has[0][0], &has[0][0] + MAXN * MAXN, false);
    fill(&rel[0][0][0], &rel[0][0][0] + MAXN * MAXN * 2, false);
    for (int i = 0; i < MAXN; ++i) { is[i][i] = true; }
}

inline void floyd(int upbound) {
    for (int i = 0; i < upbound; ++i) {
        for (int j = 0; j < upbound; ++j) {
            if (is[i][j])rel[i][j][1] = true;
            if (has[i][j])rel[i][j][0] = true;
        }
    }
    for (int k = 0; k < upbound; ++k) {
        for (int i = 0; i < upbound; ++i) {
            for (int j = 0; j < upbound; ++j) {
                if (rel[i][k][1] && rel[k][j][1])rel[i][j][1] = true;
                if ((rel[i][k][1] && rel[k][j][0]) || (rel[i][k][0] && rel[k][j][1]) ||
                    (rel[i][k][0] && rel[k][j][0]))
                    rel[i][j][0] = true;
            }
        }
    }
}

int class_flag = -1;
map<string, int> class_cnt;

inline int cls(const string &s) {
    map<string, int>::iterator it;
    if ((it = class_cnt.find(s)) != class_cnt.end())return it->second;
    else {
        class_cnt.insert(make_pair(s, ++class_flag));
        return class_flag;
    }
}

int main() {
    init();
    int n, m;
    scanf("%d%d", &n, &m);
    string c1, r, c2;
    for (int i = 0; i < n; ++i) {
        cin >> c1 >> r >> c2;
        if (r[0] == 'i') { is[cls(c1)][cls(c2)] = true; } else { has[cls(c1)][cls(c2)] = true; }
    }
    floyd(class_flag + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> c1 >> r >> c2;
        int tp = r[0] == 'i' ? 1 : 0;
        printf("Query %d: %s\n", i, rel[cls(c1)][cls(c2)][tp] ? "true" : "false");
    }
    return 0;
}

DFS的AC代码：

#include <iostream>
#include <string>
#include <map>

using namespace std;
const int MAXN = (int) 1e3 + 5;
bool is[MAXN][MAXN];
bool has[MAXN][MAXN];
bool ins[MAXN][MAXN][2];

inline void init() {
    fill(&is[0][0], &is[0][0] + MAXN * MAXN, false);
    fill(&has[0][0], &has[0][0] + MAXN * MAXN, false);
    fill(&ins[0][0][0], &ins[0][0][0] + MAXN * MAXN * 2, false);
    for (int i = 0; i < MAXN; ++i) { is[i][i] = true; }
}

int class_flag = -1;
map<string, int> class_cnt;

inline int cls(const string &s) {
    map<string, int>::iterator it;
    if ((it = class_cnt.find(s)) != class_cnt.end())return it->second;
    else {
        class_cnt.insert(make_pair(s, ++class_flag));
        return class_flag;
    }
}

void dfs(int root, int cur, int cur_type) {
    for (int i = 0; i < MAXN; ++i) {
        if (!ins[root][i][cur_type] && is[cur][i]) {
            ins[root][i][cur_type] = true;
            dfs(root, i, cur_type);
        }
        if (!ins[root][i][0] && has[cur][i]) {
            ins[root][i][0] = true;
            dfs(root, i, 0);
        }
    }
}

int main() {
    init();
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        string c1, r, c2;
        cin >> c1 >> r >> c2;
        if (r[0] == 'i') { is[cls(c1)][cls(c2)] = true; } else { has[cls(c1)][cls(c2)] = true; }
    }
    for (int i = 0; i <= class_flag; ++i) { dfs(i, i, 1); }
    for (int i = 1; i <= m; ++i) {
        string c1, r, c2;
        cin >> c1 >> r >> c2;
        int tp = r == "is-a" ? 1 : 0;
        printf("Query %d: %s\n", i, ins[cls(c1)][cls(c2)][tp] ? "true" : "false");
    }
    return 0;
}

网上能找到的别的题解都是BFS的，这里就不写了。