poj1182 266ms 并查集

没有大佬那么厉害的可以直接得出结论，只能把情况都列出来，其实一共只有18种情况，所以不妨头脑风暴一次，然后稍加整理(先根据d的值分类，再根据rank[a]的值进行分类)规律就显然了。
详细阐述下整理部分吧。
首先把d=1，2，这是两种情况，然后细分，例如，当d=1，把rank[a],rank[b],rank[x]的关系列出来，其实只有9种可能，所以一共是233=18种可能。
为了简化书写让a代替rank[a],b代替rank[b],x代替rank[x];
然后将x=0，1，2的情况列出：

然后你会发现其实当a，b一样时，x的值是与d值有关，例如，当d=1，x=1三组数据的a,b的值刚好与d=2，x=0三组数据的a,b的值有关，所以当d=2时，X2=(X1+2)%3,其中X2是当d=2，x的值，X1同理。所以我们只要讨论d=1的情况就好了。
然后我们再看当d=1的情况
当a=0,x=b;
当a=1,x=(b+2)%3
当a=2,x=(b+1)%3
然后把x的表达式与a联系起来，得到：x=(b+(3-a))%3;
所以X1=(b+(3-a))%3，X2=(b+(5-a))%3->(b+(2-a))%3
最后再把表达式同d联系起来：会惊奇地发现：x=(b+(4-d-a))%3
以上是我这个小菜鸡的表达式导出过程。
附代码：

#include<cstdio>
using namespace std;
//做了1个半小时做出来了
//感觉还是很不错的，对并查集了解更深刻了
//推理加找规律，很有意思
const int N = 5e4;
int father[N+5],rank[N+5];
//rank表示偏移量，rank[x]=y,偏移量为0同类，1为x被y吃，2为x吃y
int n;
void init(int n)
{
    for(int i = 1; i<=n; ++i)
    {
        father[i] = i;
        rank[i] = 0;
    }
}
int find(int x)
{
    if(x!=father[x])
    {
        int px = find(father[x]);
        rank[x] = (rank[x] + rank[father[x]]) % 3;
        father[x] = px;
    }
    return father[x];
}
int _union(int d,int a,int b)
{
    if(a>n||b>n)
        return 1;
    if(d==2&&a==b)
        return 1;
    int x = find(a);
    int y = find(b);
    if(x==y)
    {
        if(d==2&&(rank[a]+1)%3!=rank[b])
            return 1;
        if(d==1&&rank[a]!=rank[b])
            return 1;
    }
    else
    {
        father[x] = y;
        rank[x] = (rank[b]+(4-d)-rank[a])%3;
        //这个把结果都列出来一共 2*3*3 = 18种, 然后比较得到的规律
    }
    return 0;
}
int main()
{
    int k;
    int a,b,d;
    scanf("%d%d",&n,&k);
    init(n);
    int ans = 0;
    while(k--)
    {
        scanf("%d%d%d",&d,&a,&b);
        if(_union(d,a,b))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}