pku1703 Find them, Catch them

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

#include<stdio.h>
#include<string.h>

const int MAX=100005;
int pre[MAX];
int offset[MAX];        //相对父节点的偏移量

void initial()
{
    memset(pre,0,sizeof(pre));
    memset(offset,0,sizeof(offset));
}

int find(int x)
{
    if(!pre[x]) return x;

    int temp=pre[x];
    pre[x]=find(pre[x]);
    offset[x]=(offset[temp]+offset[x])%2;

    return pre[x];
}

void merge(int v1,int v2)
{
    int root1=find(v1);
    int root2=find(v2);

    if(root1==root2) return;
    pre[root2]=root1;
    offset[root2]=(offset[v1]+1-offset[v2])%2;
}

int main()
{
    int cases;
    scanf("%d",&cases);

    while(cases--)
    {
        initial();

        int n,m;
        scanf("%d%d",&n,&m);

        while(m--)
        {
            char str[2];
            int v1,v2;
            scanf("%s%d%d",str,&v1,&v2);

            if(str[0]=='A')
            {
                int root1=find(v1);
                int root2=find(v2);

                if(root1==root2)
                {
                    if(offset[v1]==offset[v2])
                        printf("In the same gang.\n");
                    else
                        printf("In different gangs.\n");
                }
                else
                    printf("Not sure yet.\n");
            }
            else
            {
                merge(v1,v2);
            }
        }
    }
    return 0;
}

总结：

只要两件犯罪有关联，即明确属于同一个犯罪组织和明确属于不同的犯罪组织，就将这两件犯罪放到一个集合当中，用某个对这个集合而言相对固定的标志来明确区分这两个犯罪是否属于同一个犯罪组织，可以选取并查集的树根，当两件犯罪相对树根的偏移量相同时说明其属于同一犯罪组织，不同则属于不同组织，在merge合并两个有关联的犯罪时，必须将两棵树合成一棵，即要修改某一树根的偏移量，v2移到root1中后最终的偏移量是offset[v1]+1,即v2偏移量的增量是offset[v1]+1-offset[v2],亦即对应原先每一个root2中的结点的偏移量的增量都是offset[v1]+1-offset[v2],转移后的offset[root2]=offset[v1]+1-offset[v2]+offset[root1],由于最开始每个根节点的偏移量都初始化为0,因而更新后的offset[root2]=(offset[v1]+1-offset[v2])%2,为什么只需要更新树根的偏移量？因为在find查找树根时可以自上而下的更新每个结点。对于原来合并之前的子节点v2其偏移量是offset[v2]+0,因为root2的偏移量初始为0,而后通过merge更新了offset[root2]的偏移量，对于v2只需要显式地加上offset[root2]就行。