这道题，在前一道题目的基础上，好理解多了，个人在代码中写了自己的一点理解
也算是一个拓展应用吧，个人感觉对并查集有了更深的理解了，具体怎么样，继续做题看看吧
大牛还给了一个一般情况下维护偏移量的公式
感谢这位大牛分享：
这里将两个集合并起来并将所挂集合偏移量指向：
kind[b]=(kind[x]-kind[y]+4)%3;
想想上一题是不是也很类似呢
其实上一题的公式也可以改成
kind[b]=(kind[x]-kind[y]+3)%2;
不管是几个动物循环，都能得到类似的结论，所以以后碰到4，5，6，7。。。个动物的食物链，你应该也会做了吧？^_^
View Code
#include<stdio.h>
#define MAXN 50010
int f[MAXN],r[MAXN],n;
int find(int x)
{
if(x==f[x])
return x;
int t=find(f[x]);
r[x]=(r[x]+r[f[x]])%3;//由x与父节点的关系以及父节点与根节点的关系，推出x与根节点的关系
f[x]=t;
return f[x];
}
int Union(int x,int y,int c)
{
if(x>n||y>n)
return 1;
int a=find(x),b=find(y);
if(c==1)
{
if(a==b)
{
if(r[x]!=r[y])//不同类的情况
return 1;
}
else {
f[b]=a;
r[b]=(r[x]-r[y]+3)%3;
//x与y为同类的情况，注意，将a并到b上，与将b并到a上对应的公式是不同的
//再补充一下，突然发现，还可以理解，这里由于x与y已经为同类的了，所以还是可以推出来的
}
}
else {
if(x==y) return 1;//自己吃自己，属于假话
if(a==b)
{
if((r[x]+1)%3!=r[y])
//r[x]+1==r[y]表示x吃y,当然，还要考虑r[x]==2,r[y]==0的情况，所以对3取模
return 1;
}
else {
f[b]=a;
r[b]=(r[x]-r[y]+4)%3;
//公式，具体如何推来的，额，还没发现过有大牛解释，不过，结合上一篇文章的解释，还是可以理解的
}
}
return 0;
}
int main()
{
int i,k,c,x,y,sum=0;
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=0;
}
for(i=1;i<=k;i++)
{
scanf("%d %d %d",&c,&x,&y);
if(Union(x,y,c))//返回值为真，则累加
sum++;
}
printf("%d\n",sum);
return 0;
}
以上部分解释来自此链接http://www.cppblog.com/abilitytao/archive/2010/05/14/98899.html
hdu3047Zjnu Stadium
题意：已知Ｎ个人围成一个圈，现在给出ｍ条指令，形如Ａ,Ｂ,Ｃ，即Ｂ在Ａ的顺时针方向第Ｃ个
判断中间有几条指令是错误的
分析：很明显的用并查集俩做，根据指令，用一个ｒ［］数组保存每一个人到根节点的相对位置，
这样，每给出一条指令，若俩个人在同一个集合，则可以根据他们各自的到根节点的距离计算出是否与指令一致
若不在同一个集合，则合并，同时计算俩个集合的根节点的相对距离，，其余节点之间的相对距离在找出过程中计算，这个跟之前的题目类似。
忽略了一点，狂ＷＡ 了啊，就是这Ｎ个人是围成圈的，所有计算相对距离的时候要ｍｏｄ３００
View Code
#include<iostream>
#include<algorithm>
#define MAXN 50000+10
using namespace std;
int f[MAXN],r[MAXN],n,m;
void init()
{
for(int i=0;i<=n;i++)
{
f[i]=i;
r[i]=0;
}
}
int find(int x)
{
if(x==f[x])
return f[x];
int t=find(f[x]);
r[x]=(r[x]+r[f[x]])%300;
f[x]=t;
return f[x];
}
bool Union(int x,int y,int w)
{
int a=find(x);
int b=find(y);
if(a==b)
{
if((r[y]-r[x]+300)%300==w)
return true;
return false;
}
f[b]=a;
r[b]=(r[x]+w-r[y]+300)%300;
return true;
}
int main()
{
int a,b,c;
while(scanf("%d %d",&n,&m)==2)
{
int ans=0;
init();
while(m--)
{
scanf("%d %d %d",&a,&b,&c);
if(!Union(a,b,c))
ans++;
}
printf("%d\n",ans);
}
return 0;
}