POJ 1182 食物链 【带权并查集/补集法】

时间：2022-11-21 19:37:12
动物王国中有三类动物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

【洛谷】https://www.luogu.org/problemnew/show/P2024

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<(n); i++)

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxn = 1e5 + ;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

int dir[][] = {{,},{,-},{-,},{,}};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

int n,m,d,x,y;

int fa[maxn*];

inline int read()

{

    int sum=;

    char ch=getchar();

    while(ch>''||ch<'') ch=getchar();

    while(ch>=''&&ch<='') sum=sum*+ch-,ch=getchar();

    return sum;

}

int Find(int x)

{

    return fa[x]==x ? x:fa[x]=Find(fa[x]);

}

void join(int x,int y)

{

    int fx=Find(x);

    int fy=Find(y);

    fa[fx]=fy;

}

int main()

{

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

    int ans=;

    for(int i=;i<=*n;i++) fa[i]=i;

    for(int i=;i<=m;i++)

    {

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

        if(x>n||y>n){ans++;continue;}

        if(d==)

        {

            if(Find(x+n)==Find(y) || Find(x+*n)==Find(y)) {ans++;continue;}

            join(x,y); join(x+n,y+n); join(x+*n,y+*n);

        }

        else if(d==)

        {

            if(Find(x)==Find(y) || Find(x+*n)==Find(y)) {ans++;continue;}

            join(x,y+*n); join(x+n,y); join(x+*n,y+n);

        }

    }

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

    return ;

}

/*

【题意】

略

【类型】

带权并查集

【分析】

对于每种生物：设 x 为本身，x+n 为猎物，x+2*n 为天敌

【时间复杂度&&优化】

【trick】

【数据】

*/

相关文章