并查集经典题
1. 向量的思考模式
2. 再计算向量时，要画图；有一个关系一开始写错了
3. 本人的norm函数一开始x >= 3写成了 x>3，应该对这种小函数多做UT（口头上的，比如）
4. 可以把father set一开始memset为-1
参考链接
http://blog.csdn.net/tiantangrenjian/article/details/7085575
http://pdjlzs.diandian.com/post/2012-02-03/15719424
#include <iostream>
using namespace std; #define ANI_MAX (50000 + 10) int ss[ANI_MAX];
int rk[ANI_MAX]; int norm(int x)
{
if (x >= 3)
{
x = x % 3;
}
else if (x < 0)
{
while (x < 0)
{
x += 3;
}
}
return x;
} void init()
{
for (int i = 0; i < ANI_MAX; i++)
{
ss[i] = i;
}
memset(rk, 0, sizeof(rk));
} int find(int x)
{
if (ss[x] == x)
{
return x;
}
else
{
int r = find(ss[x]);
rk[x] = norm(rk[x] + rk[ss[x]]);
ss[x] = r;
return r;
}
} bool merge(int x, int y, int type)
{
int fx = find(x);
int fy = find(y);
if (fx == fy)
{
if (norm(rk[y] - rk[x]) != type)
{
return true;
}
else
{
return false;
}
} ss[fy] = fx;
rk[fy] = norm(rk[x] - rk[y] + type);
return false;
} int main(void)
{
int n;
int k;
scanf("%d %d",&n,&k);
int error = 0;
init();
for (int i = 0; i < k; i++)
{
int d;
int x;
int y;
scanf("%d %d %d",&d,&x,&y);
if (x > n || y > n || (d == 2 && x == y))
{
error++;
continue;
}
else if (merge(x, y, d - 1))
{
error++;
} } cout << error << endl; return 0;
}