这是一题相当有水平的并查集问题。虽然我一次性ac，但是基本上是没有任何思路搜索了一下牛人思路才过的。
思考这题时，我陷入到了以下怪圈：
1.并查集应该是无限的，但是貌似这题的并集只有三个
2.当两者关系未被确认是哪个集合时，会出现无限多的临时子集
3.如何表示临时子集
看了看牛人的思路，相当巧妙：并查集基本还是无限集，有限集用关系向量来表示。
1.使用关系向量的方法，让我获益匪浅。
2.计算关系向量的方法，又如此的巧合。
3.并查集并不一定是相同的才并一起，又回归到第一点，当关系向量可以用有限集表示时，并查集里的元素可以不是同一类元素。
最后还要说，这题相当牛B.
#include "stdio.h"
#define MAX 50001
#define Similar 0
#define Enemy 1
#define Food 2
// Food eat Enemy
// Enemy eat Similar
// Similar eat Food
struct _xtree
{
int parent;
int relation;
}xtree[MAX];
int N, K;
void build()
{
int i;
for (i = 1; i <= N; i++)
{
xtree[i].parent = i;
xtree[i].relation = Similar;
}
}
int find(int i)
{
int p = xtree[i].parent;
if (p != i)
{
xtree[i].parent = find(xtree[i].parent);
xtree[i].relation = (xtree[p].relation + xtree[i].relation) % 3;
}
return xtree[i].parent;
}
int check(int x, int y, int r)
{
int root_x, root_y, root_r;
if (x > N || y > N)
{
return 0;
}
root_x = find(x);
root_y = find(y);
if (root_x == root_y) // x relate y
{
return (xtree[x].relation - xtree[y].relation + 3) % 3 == r ? 1 : 0;
}
else
{
root_r = (xtree[y].relation + r + (3 - xtree[x].relation)) % 3;
xtree[root_x].parent = root_y;
xtree[root_x].relation = root_r;
return 1;
}
}
void main()
{
int op, x, y;
int count = 0;
scanf("%d %d", &N, &K);
build();
while (K--)
{
scanf("%d %d %d", &op, &x, &y);
if (!check(x, y, op == 1 ? Similar : Enemy))
{
count++;
}
}
printf("%d\n", count);
}posted on 2010-08-28 21:11
margin 阅读(157)
评论(0) 编辑 收藏 引用