2014-12-11-19:49-update
两份完全一模一样的代码,在杭电提交C++编译器AC,G++编译器WA。是不是杭电服务器收到远自一千亿光年外的天体发来的宇宙射线干扰,导致评测机抽风啊。代码完全没有问题,POJ验证过
这么个问题坑了一晚上我是始料未及的。
下午又去了去年去过的M50园区木马设计公司,师哥说我们长大了不少。变化有这么大吗。
2015-12-11-19:41-update
一个不应该用并查集做的题目被我硬生生用并查集做出来了。。
HDU3786: 找出直系亲属
写完代码自己胡乱编了两组测试数据程序运行死活出不了结果,拿纸把测试数据画了画才发现两组测试数据一组数据节点关系高了个“离婚后再婚又生了好几个孩子”,另一组数据直接成了一个孙子有三个爷爷--<--<-<@ 数据不能乱编
2014-12-11-19:49-update
细想这不是并查集了,算是一直在维护一棵树,不管是增还是查,都从这个棵树增加或查找信息。
/*CPP code*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXM 200
using namespace std;
int _parent[MAXM];
void init_tree()
{
for (int i = 0; i <= MAXM; i++)
{
_parent[i] = i;
}
}
int find_parent(int i)
{
if (_parent[i] == i)
return i;
else
return find_parent(_parent[i]);
}
int is_parent(int i, int root, int tar)
{
if (i == tar)
return 1;
if (i == root)
return 0;
return is_parent(_parent[i], root, tar);
}
int find_top(int a, int b, int top = 1)
{
if (_parent[a] == b)
return top;
else
return find_top(_parent[a], b, top + 1);
}
void union_parent(int a, int b, int c)
{
_parent[b] = a;
_parent[c] = a;
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) == 2)
{
if (n == 0 && m == 0)
break;
init_tree();
char a,b,c;
while(n--)
{
cin >> a >> b >> c;
union_parent(a, b, c);
}
while(m--)
{
int flag = 1;
int flag2 = -1;
int tot = 1;
cin >> a >> b;
if (is_parent(a, find_parent(a), b))
{
tot = find_top(a, b);
flag2 = 1;
}else
if (is_parent(b, find_parent(b), a))
{
tot = find_top(b,a);
}
else
flag = 0;
if (flag)
{
if (tot > 2)
{
for (tot -= 2; tot > 0; tot--)
cout << "great-";
cout << "grand";
}
else if (tot == 2)
{
cout << "grand";
}
if (flag2 > 0)
cout << "parent" << endl;
else
cout << "child" << endl;
}
else
cout << "-" << endl;
}
}
return 0;
}