题解 | #找出直系亲属#

手贱，把这段代码写成了一个函数。然后导致了超时。

咱以后能写在主函数里的就写在主函数。函数调用如果在循环里，读入读出内存很耗时间。

        if (father != '-') {
            son[father - 'A'] = child - 'A';
        }
        if (mother != '-') {
            son[mother - 'A'] = child - 'A';
        }

放到主函数里面就不超时了。。。

#include <iostream>

using namespace std;

const int MAXN = 30;

int son[MAXN];

//判断两个人是否有亲缘关系以及相差的代数
int Generation(int x, int y) {
    int level = 0;
    int a = x;
    while (son[a] != a) {
        a = son[a];
        level++;
        if (a == y) {//找到x的直系后代为y了，返回层数
            return level;
        }
    }

    level = 0;
    int b = y;
    while (son[b] != b) {
        b = son[b];
        level--;
        if (b == x) {//找到y的直系后代为x了，返回层数
            return level;
        }
    }

    return 0;//都没找到
}

//判断两个人的亲缘关系
string Relationship(int level) {
    string answer;
    if (level == 0) {//没有亲缘关系
        answer = "-";
    } else if (level == 1) {
        answer = "parent";
    } else if (level == 2) {
        answer = "grandparent";
    } else if (level > 2) {
        for (int j = 0; j < level - 2; ++j) {
            answer += "great-";
        }
        answer += "grandparent";
    } else if (level == -1) {
        answer = "child";
    } else if (level == -2) {
        answer = "grandchild";
    } else if (level < -2) {
        for (int j = 0; j < -2 - level; ++j) {
            answer += "great-";
        }
        answer += "grandchild";
    }
    return answer;
}

int main() {
    int n;//n个亲属关系
    int m;//m个问题
    while (scanf("%d%d", &n, &m) != EOF) {
        //初始化
        for (int i = 0; i < MAXN; ++i) {
            son[i] = i;
        }
        //录入信息
        for (int i = 0; i < n; ++i) {
            char child, father, mother;
            cin >> child >> father >> mother;
/*            if (father - 'A' != '-') {
                son[father - 'A'] = child - 'A';
            }
            if (mother - 'A' != '-') {
                son[mother - 'A'] = child - 'A';
            }*/
            if (father != '-') {
                son[father - 'A'] = child - 'A';
            }
            if (mother != '-') {
                son[mother - 'A'] = child - 'A';
            }
        }

        //查询亲属关系
        for (int i = 0; i < m; ++i) {
            char p1, p2;
            cin >> p1 >> p2;
            int level = Generation(p1 - 'A', p2 - 'A');//判断亲属关系
            cout << Relationship(level) << endl;
        }
    }
    return 0;
}