种类并查集

#include <iostream>
using namespace std;

const int M = 50000 + 10;

struct Node
{
    int father;
    int kind;
}node[M];

void Init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        node[i].father = i;
        node[i].kind = 0;
    }

}
//
int Find(int x)
{
    if (x == node[x].father)
    {
        return x;
    }

    int temp = node[x].father;//temp保存原来的老爸

    node[x].father = Find(node[x].father);

    node[x].kind = (node[x].kind + node[temp].kind) % 3;//////////////

    return node[x].father;
}

//
void Union(int rootx, int rooty, int x, int y, int k)//k == 0:a==b  k == 1:a > b
{

    node[rooty].father = rootx;
    node[rooty].kind = (-k +(node[x].kind - node[y].kind)+3)%3;///////////////

}
//(node[a].kind - node[b].kind + 3) % 3 == 1表示a > b
//node[a].kind == node[b].kond 表示 a == b
//为了方便操作根结点的种类是0
//与根结点直接相连的节点与根结点的关系是正确的
//在同一颗树上的结点表示存在关系

附带文章：http://www.cppblog.com/tortoisewu/archive/2009/07/14/85501.html

http://www.cppblog.com/tortoisewu/archive/2009/05/29/86110.html