pku1182 食物链

时间：2010-09-20 来源：Z_Q_2010

#include<stdio.h>

const int Maxn=50002;
int n,m,num;
int pre[Maxn];
int offset[Maxn];

void initial()
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=-1;
        offset[i]=0;
    }
}

int find(int x)
{
    if(pre[x]<0) return x;
    int temp=pre[x];
    pre[x]=find(temp);
    offset[x]=(offset[x]+offset[temp])%3;
    return pre[x];
}

void merge(int d,int x,int y)
{
    if(x>n||y>n)
    {
        num++;
    }
    else
    {
        if(d==1)
        {
            int root1=find(x),root2=find(y);
            if(root1==root2)    //一旦属于同一个集合，就需需要判断是否为谎言，否则只需合并集合

            {
                if(offset[x]!=offset[y]) num++;
            }
            else
            {
                if(pre[root1]<pre[root2])
                {
                    pre[root1]=pre[root1]+pre[root2];
                    pre[root2]=root1;
                    offset[root2]=(offset[x]-offset[y]+3)%3;
                }
                else
                {
                    pre[root2]=pre[root2]+pre[root1];
                    pre[root1]=root2;
                    offset[root1]=(offset[y]-offset[x]+3)%3;
                }
            }
        }
        else
        {
            if(x==y) num++;
            else        //x吃y->offset[y]=offset[x]+1;

            {
                int root1=find(x),root2=find(y);
                if(root1==root2)
                {
                    if(offset[y]!=(offset[x]+1)%3) num++;
                }
                else
                {
                    if(pre[root1]<pre[root2])
                    {
                        pre[root1]=pre[root1]+pre[root2];
                        pre[root2]=root1;
                        offset[root2]=(offset[x]+1-offset[y]+3)%3;
                    }
                    else
                    {
                        pre[root2]=pre[root2]+pre[root1];
                        pre[root1]=root2;
                        offset[root1]=(offset[y]-1-offset[x]+3)%3;
                    }
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    int d,x,y;
    initial();
    while(m--)
    {
        scanf("%d%d%d",&d,&x,&y);
        merge(d,x,y);
    }
    printf("%d\n",num);
    return 0;
}

总结：

通过相对树根的偏移量来标记位于同一个集合中的两个结点之间的实际关系，在merge更改一个树根root2的偏移量时，可以先确定y在root1中的最终偏移量，在确定y的偏移量的增量，而root2中每一个结点都加上给增量即成功地将root2合并到root1集合中。在find中必须从上而下的更新每个结点的偏移量，每一原先root2中的子结点的偏移量都加上offset[root2]这个更新后的偏移量的绝对量。