POJ 1182 食物链 经典并查集+关系向量简单介绍

时间：2021-11-06 05:51:28

题目：

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述： 
第一种说法是"1 X Y"，表示X和Y是同类。 
第二种说法是"2 X Y"，表示X吃Y。 
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 
1） 当前的话与前面的某些真的话冲突，就是假话； 
2） 当前的话中X或Y比N大，就是假话； 
3） 当前的话表示X吃X，就是假话。 
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。 

Input

第一行是两个整数N和K，以一个空格分隔。 
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。 
若D=1，则表示X和Y是同类。 
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。
思路分析：
首先我们应该找出什么情况下会产生错误：
1.因为给出的所有动物都属于A,B,C中的某一类，那么也就是说如果a∈A，b∈B，c∈C，那么如果a吃b，b吃c，那么c一定吃a，否则产生错误的。
2.如果输入时x，y 是存在吃或被吃的关系，但是在之前我们发现他们是同类，此时产生错误。
当我们找到了错误产生的原因后，我们很容易发现我们需要一个relation[]数组，来储存x与它的根节点rt的关系。
关系一共有三种：
1.x与rt同类
2.x吃rt
3.x被rt吃
所以我们可以用数字0,1,2 分别代表这三种关系（不可随意替代，必须按此顺序，具体原因很简单，试着推一下吧~）
下面讲一下关系向量：
POJ 1182 食物链 经典并查集+关系向量简单介绍

很明显 A->C = A->B + B->C,因为我们用0-2代表关系，所以A->C=(A->B+B->C)%3；

但是如果输入的两个数据a，b的根节点并不相同，那么我们就应该求出x的根节点ra与y的根节点rb的关系了，已经利用向量来解决

POJ 1182 食物链 经典并查集+关系向量简单介绍

ra->rb=ra->b+b->rb

b->rb我们在Find数组里已经更新出

ra->b=a->b - a->ra

a->b=op-1(op为输入时给出的关系)

所以：ra->rb = ((op-1-a->ra+3)%3+b->rb)%3.

恩说道这里差不多很明白了吧，如果有疑问详细看代码吧~

#include<cstdio>

#include<stdio.h>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

#define MAX 1000005

using namespace std;

int father[MAX],relation[MAX];//relatio输出某点与其根节点的关系

int Find(int x)

{

    int k=father[x];

    if(x!=father[x])

    {

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

        relation[x]=(relation[x] + relation[k])%;//更新x与根节点的关系

    }

    return father[x];

}

int main()

{

    int n,k,i,ans,op,x,y;

    scanf("%d%d",&n,&k);

    ans=;

    for(i=; i<=n; i++)

    {

        father[i]=i;

        relation[i]=;

    }

    for(i=; i<=k; i++)

    {

        scanf("%d%d%d",&op,&x,&y);

        int f1=Find(x);

        int f2=Find(y);

        if(x>n || y>n || (op== && x==y))//如果x，y是同类他们肯定不会吃对方

            ans++;

        else if(f1==f2 && relation[x]!=(relation[y]-+op)%)//如果它们的根节点相同，然而relation[x]却与通过y求出的x与根节点的关系矛盾，则产生错误

            ans++;

        else if(f1!=f2)

        {

            father[f1]=f2;

            relation[f1]=((op--relation[x]+)% + relation[y])%;//求出f1与f2之间的关系

        }

    }

    printf("%d\n",ans);

    return ;

}

相关文章