Is-A? Has-A? Who Knowz-A?【传递闭包】

题目：

Two familiar concepts in object oriented programming are the is-a and has-a relationships. Given two classes A and B, we say that A is-a B if A is a subclass of B; we say A has-a B if one of the fields of A is of type B. For example, we could imagine an object-oriented language (call it ICPC++) with code like that in Figure E.1, where the class $D a y$ is-a $T i m e$ , the class $A p p o i n t m e n t$ is both a $D a t e B o o k$ and a $R e m i n d e r$ , and class $A p p o i n t m e n t$ has-a $D a y$ .

These two relationships are transitive. For example if A is-a B and B is-a C then it follows that A is-a C. This holds as well if we change all the is-a’s in the last sentence to has-a’s. It also works with combinations of is-a’s and has-a’s: in the example above, $A p p o i n t m e n t$ has-a $T i m e$ , since it has-a $D a y$ and $D a y$ is-a $T i m e$ . Similarly, if class $D a t e B o o k$ has-a $Y e a r$ then $A p p o i n t m e n t$ has-a $Y e a r$ , since $A p p o i n t m e n t$ is-a $D a t e B o o k$ .
In this problem you will be given a set of is-a and has-a relationships and a set of queries of the form $A$ is/has-a $B$ . You must determine if each query is true or false.
$1 \leq n, m \leq 10000$ ,最多 $500$ 个名称。

分析：

一开始想到的是建一个图，然后按照关系建了两种边，然后用 $d f s$ 判断询问的两点中，一个点能不能到达另一个点。但这样的话边的情况会复杂，容易出错。求两点之间的可达关系，直接求传递闭包即可，更新条件见代码。
复杂度： $O (50 0^{3})$

#include <bits/stdc++.h>
using namespace std;
const int N=510;
bool pa[N][N],pb[N][N];
map<string,int>mp;
int cnt;
void solve()
{
    for(int k=1;k<=cnt;k++)
    {
        pa[k][k]=1;
        for(int i=1;i<=cnt;i++)
        {
            for(int j=1;j<=cnt;j++)
            {
                if(pa[i][k]&&pa[k][j])
                    pa[i][j]=1;
                if(pa[i][k]&&pb[k][j]||pb[i][k]&&pa[k][j]||pb[i][k]&&pb[k][j])
                    pb[i][j]=1;
            }
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    string a,r,b;
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>r>>b;
        if(mp[a]==0)
            mp[a]=++cnt;
        if(mp[b]==0)
            mp[b]=++cnt;
        if(r.compare("is-a")==0)
            pa[mp[b]][mp[a]]=1;
        else
            pb[mp[b]][mp[a]]=1;
    }
    solve();
    for(int i=1;i<=m;i++)
    {
        printf("Query %d: ",i);
        cin>>a>>r>>b;
        if(r.compare("is-a")==0)
        {
            if(pa[mp[b]][mp[a]])
                printf("true\n");
            else
                printf("false\n");
        }
        else
        {
            if(pb[mp[b]][mp[a]])
                printf("true\n");
            else
                printf("false\n");
        }
    }
    return 0;
}