题目链接:
http://poj.org/problem?id=1182
题意:
题解:
大牛题解：http://blog.csdn.net/niushuai666/article/details/6981689
合并： d-1是偏移量，ra->rb, ra作为rb的父亲，注意方向【箭头是把右边合并到左边】
向量的思想：
if(ra!=rb)不在一个集合里，合并 fa[rb]=ra，还需要更新r[rb]，即与新的父节点(ra)的关系
r[rb] = ra->rb = ra->a+a->b+b->rb = r[a]+(d-1)-r[b];
fa[rb] = ra;
r[rb] = (r[a]+d-1-r[b]+3)%3;if(ra==rb) 不需要合并了，判断是否矛盾，依然是向量的偏移量思想
a->b = a->ra+ra->b = -r[a]+r[b];
判断 -r[a]+r[b] 是否等于 d-1(偏移量)
if((r[b]-(d-1)+3)%3 != r[a]) ans++;find操作，把信息传下来，路径压缩
向量思想： R表示根节点，t表示当前x的父节点，现在要实现R->x(把x压缩到根节点)
那么 R->x = R->t+t->x = r[t]+r[x]。 把这个值依次传下来。
r[x] = (r[x]+r[t])%3;代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 #define MS(a) memset(a,0,sizeof(a)) 8 #define MP make_pair 9 #define PB push_back 10 const int INF = 0x3f3f3f3f; 11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 12 inline ll read(){ 13 ll x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 ////////////////////////////////////////////////////////////////////////// 19 const int maxn = 5e4+10; 20 21 int fa[maxn],r[maxn]; 22 23 int find(int x){ 24 if(fa[x] == x) return x; 25 int t = fa[x]; 26 fa[x] = find(fa[x]); 27 r[x] = (r[x]+r[t])%3; 28 return fa[x]; 29 } 30 31 int main(){ 32 int n,k; 33 scanf("%d%d",&n,&k); 34 for(int i=0; i<=n; i++) fa[i]=i,r[i]=0; 35 int ans = 0; 36 for(int i=0; i<k; i++){ 37 int d,a,b,ra,rb; 38 scanf("%d%d%d",&d,&a,&b); 39 if(a>n || b>n) { ans++; continue;} 40 if(d==2 && a==b) { ans++; continue;} 41 ra = find(a),rb = find(b); 42 if(ra == rb){ 43 if((r[b]-(d-1)+3)%3 != r[a]) ans++; 44 } 45 else{ 46 fa[rb] = ra; 47 r[rb] = (r[a]+d-1-r[b]+3)%3; 48 } 49 } 50 51 cout << ans << endl; 52 53 return 0; 54 }