L2-030 冰岛人 (25 分)

题目

题目链接

题解

STL。

保存关系时，我们让儿子指向父亲，而不是父亲指向儿子，一个儿子有一个父亲，但一个父亲有多个儿子。查询时，两个人不停地向上找父亲，如果存在一个人的五代内的祖先与另一个人的某个祖先是同一个人，则false，如果没找到，则true。

最开始我使用邻接表，再两次bfs，第一次bfs标记第一个人五代内的祖先，第二次bfs找第二个人五代内的祖先是否被标记，存在被标记说明不可行，否则可行。

判断方式已经出现了问题，题目要求所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。，这句话的含义是可能存在二者的公共祖先是a的曾曾曾……曾祖父，是b的祖父，这样一来虽然祖先不是a的五代内的祖先，但却是b五代内的祖先，所以这种情况也要输出yes。如果单纯使用上面的bfs是不能实现的。

代码

#include
using namespace std;

const int N = 1e6+10;

int n, k;

struct node {
	bool sex;
	string fa = "";
};

map peo;

string getlastname (string s) {
	char ch = s.back();
	if (ch == 'f' || ch == 'm') return "";
	return s.substr (0, s.size() - (ch == 'n' ? 4 : 7));
}

bool check (string a, string b) {
	int i = 1;
	for (string x = a;x.size();x = peo[x].fa, i ++) {
		int j = 1;
		for (string y = b;y.size();y = peo[y].fa, j ++) {
			if (i >= 5 && j >= 5) break;
			if (x == y) return false;
		}
	}
	return true;
}

int main()
{
	cin >> n;
	for (int i = 0;i > fn >> ln;
		peo[fn].sex = (ln.back() == 'm' || ln.back() == 'n');
		peo[fn].fa = getlastname(ln);
//		cout  afn >> aln >> bfn >> bln;
		if (peo.find (afn) == peo.end() || peo.find (bfn) == peo.end()) puts ("NA");
		else if (peo[afn].sex == peo[bfn].sex) puts ("Whatever");
		else if (check (afn, bfn)) puts ("Yes");
		else puts ("No");
	}
	return 0;
}