POJ 1182 食物链（并查集）

时间：2023-02-03 10:57:29


Description

动物王国中有三类动物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

只有一个整数，表示假话的数目。

Sample Input

100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5

Sample Output

3

首先要意识到本题是路径压缩并查集问题。对于任意节点X与Y，只要X与Y在同一个分量中，就表示他们之间的关系是已知的(可以通过中间节点推出来)。

        设节点A->节点B的值=节点A与节点B的关系：

        A->B==0 表示A与B同类，此时B->A也==0(B与A同类)。

        A->B==1表示A吃B，此时B->A==2(B被A吃)。

        A->B==2表示A被B吃，此时B->A==1(B吃A)。

        通过任意A->B和B->C的关系，我们能推出A->C的关系。通过任意A与B关系，B与C关系，C与D关系我们能推出A与D关系。因为A->B的值等于B->A的值的逆(想想是不是)。

        分析到此我们可以用一般的路基压缩并查集来做本题，即：

        findset(x)时，先找出x的父亲节点->根的关系v2，然后用r[x](表x到x父亲的关系)与v2合并可以得出x到根的关系。比如x->父==1时，父->根==1时，那么x->根==2(想想是不是)。

        对于bind(u，v，relation)来说，只要找出u->u分量根的关系，v->v分量根的关系，且利用u与v的关系relation，可以推断出u分量根fu与v分量根fv的关系。

        对于并查集的基础结构就做完了，当如果输入r x y时，且x与y在同一分量(x与y的关系可推断出)，那么只要x与y的关系与r所指关系不同，那么说明本句是假话。另外两种假话情况很简单就不讨论了。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
const int INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
const int maxn=50000+5;
int fa[maxn];
int r[maxn];//与父的关系

int rev(int val)//返回逆向关系
{
    return (3-val)%3;
}

int rela_2(int v1,int v2)//由两个连续关系推出1个直接关系
{
    if(v1==0) return v2;
    if(v2==0) return v1;
    if(v1==1 && v2==1) return 2;
    if(v1==1 && v2==2) return 0;
    if(v1==2 && v2==1) return 0;
    if(v1==2 && v2==2) return 1;
}

int rela_3(int v1,int v2,int v3)//3间接关系推1直接关系
{
    return rela_2(rela_2(v1,v2),v3);
}

int findset(int x)
{
    if(fa[x]==-1) return x;

    int root=findset(fa[x]);
    r[x] = rela_2(r[x],r[fa[x]]);
    return fa[x]=root;
}

int bind(int u,int v,int relation)
{
    int fu=findset(u);
    int fv=findset(v);
    if(fu!=fv)
    {
        r[fu]=rela_3(rev(r[u]), relation, r[v]);
        fa[fu]=fv;
        return 0;
    }
    else//u与v在同一连通分量
    {
        if(rela_2(r[u], rev( r[v] ) ) != relation) return 1;
        return 0;
    }
}

int main()
{
    int n,k;
    int cnt=0;//假话数
    scanf("%d%d",&n,&k);
    memset(fa,-1,sizeof(fa));
    memset(r,0,sizeof(r));
    while(k--)
    {
        int relation,x,y;
        scanf("%d%d%d",&relation,&x,&y);
        relation--;//这里记得减1
        if(x>n || y>n || (relation==2 && x==y) )
        {
            ++cnt;
            continue;
        }
        cnt += bind(x,y,relation);
    }
    printf("%d\n",cnt);
    return 0;
}

 

标签：

相关文章