POJ 1182 并查集之食物链

准备

有三种动物A,B,C，假设有A->B,B->C，那么有C->A。

关系递推式：如果用R(x,y)表示x和y之间的关系，0表示同类，1表示x->y，2表示x<-y，那么有

　　　　　　　　R(x,z) = R(x,y) + R(y,z)，如下表格

　　　　　　　   

所以，对不不再一个集合中的两个元素x,y，R(x,y) = R(x,rx) + R(rx,ry) + R(ry,y)。

练手

POJ 1182 食物链

1 TLE 原因是输入的时候是先输入d，我写成了scanf("%d%d%d", &x, &y, &d);

优化：参考了杭杰的ppt，在每次查找时顺便更新父节点为根节点，同时也要更新与父节点的关系为与根节点的关系。

# include <stdio.h>

typedef struct {
    int p;
    int r;
}node;

node a[50005];

void intit(int n)
{
    int i;
    for ( i = 1; i <= n; ++i)
    {
        a[i].p = i;
        a[i].r = 0;
       }
}

int find_update(int x)
{
    int f;
    
    f = a[x].p;
    while (f != a[f].p)
    {
        a[x].p = a[f].p;
        a[x].r = (a[x].r + a[f].r)%3;
        f = a[x].p;
    }
    return f;
}

void set_union(int x, int y, int d)
{
    int rx;
    
    rx = a[x].p;
    a[rx].p = a[y].p;
    a[rx].r = (3-a[x].r+d+a[y].r)%3;
}

int main()
{
    int n, k, x, y, d, c, i;
        
    c = 0;
    scanf("%d%d", &n, &k);
    intit(n);
    for ( i = 1; i <= k; ++i)
    {
        scanf("%d%d%d", &d, &x, &y);
        if (x>n || y>n || (x == y && d != 1)) ++c;
        else if (find_update(x) != find_update(y)) set_union(x, y, d-1);
        else if (d-1 != (a[x].r+3-a[y].r)%3) ++c;
    }
    printf("%d\n", c);
    
    return 0;
}