ECNA 2017 Problem E: Is-A? Has-A? Who Knowz-A? BFS

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 Day is-a Time, the class Appointment is both a DateBook and a Reminder, and
class Appointment has-a Day.
class Day extends Time class Appointment extends Datebook, Reminder
{ {
… private Day date;
} …
}
Figure E.1: Two ICPC++ classes.
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, Appointment has-a Time, since it has-a Day and Day is-a
Time. Similarly, if class DateBook has-a Year then Appointment has-a Year, since Appointment
is-a DateBook.
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.
Input:
Input starts with two integers n and m, (1 ≤ n, m ≤ 10 000), where n specifies the number of given is-a
and has-a relationships and m specifies the number of queries. The next n lines each contain one given
relationship in the form c1 r c2 where c1 and c2 are single-word class names, and r is either the string “is-a”
or “has-a”. Following this are m queries, one per line, using the same format. There will be at most 500
distinct class names in the n + m lines, and all class names in the last m lines will appear at least once in the
initial n lines. All is-a and has-a relationships between the given classes can be deduced from the n given
relationships. Is-a relationships can not be circular (apart from the trivial identity “x is-a x”).
Output
For each query, display the query number (starting at one) and whether the query is true or false.
ECNA 2017 Problem E: Is-A? Has-A? Who Knowz-A? 9
Sample Input 1 Sample Output 1
5 5
Day is-a Time
Appointment is-a Datebook
Appointment is-a Reminder
Appointment has-a Day
Datebook has-a Year
Day is-a Time
Time is-a Day
Appointment has-a Time
Appointment has-a Year
Day is-a Day
Query 1: true
Query 2: false
Query 3: true
Query 4: true
Query 5: true

注意到：
is+is->is;has+has->has; 只要有一个边是has ，路径就是has

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 60005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>



ll quickpow(ll a, ll b) {
    ll ans = 1;
    a = a % mod;
    while (b > 0) {
        if (b % 2)ans = ans * a;
        b = b / 2;
        a = a * a;
    }
    return ans;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int n, m;
map<string, int>mp;
int vis[1000][1000][20];
int id = 1;
int iseg[1000][1000];
int haseg[1000][1000];

void num(string s) {
    if (mp.count(s))return;
    else mp[s] = id++;
}

void bfs(int x) {
    queue<pii>q;
    vis[x][x][0] = 1;
    q.push({ x,0 });
    while (!q.empty()) {
        pii tmp = q.front();
        q.pop();
        for (int i = 1; i < id; i++) {
            if (iseg[tmp.first][i] && !vis[x][i][tmp.second]) {
                vis[x][i][tmp.second] = 1;
                q.push({ i,tmp.second });
            }
            if (haseg[tmp.first][i] && !vis[x][i][1]) {
                vis[x][i][1] = 1;
                q.push({ i,1 });
            }
        }
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    cin >> n >> m;
    int i, j;
    while (n--) {
        string a, b, c;
        cin >> a >> b >> c;
        num(a);
        num(c);
        if (b[0] == 'i') {
            iseg[mp[a]][mp[c]] = 1;
        }
        else {
            haseg[mp[a]][mp[c]] = 1;
        }
    }
    for (i = 1; i < id; i++)bfs(i);
    for (i = 1; i <= m; i++) {
        string a, b, c;
        cin >> a >> b >> c;
        if (b[0] == 'i') {
            printf("Query %d: %s\n", i, vis[mp[a]][mp[c]][0] ? "true" : "false");
        }
        else {
            printf("Query %d: %s\n", i, vis[mp[a]][mp[c]][1] ? "true" : "false");
        }
    }

}