牛客算法竞赛入门课第四节习题 并查集

食物链

题目描述

现有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），输出假话的总数。

输入描述:

输出描述:

题解

完全合并

就是开一个3 * n 的数组，分别表示为三种的情况，

那么我们来看一下哪些情况是同类
（1）a吃c，b也吃c，则a和b同类；
（2）a吃c，c吃d，d吃b，则a和b同类；

我们就将a ， b，和 a + n ,b +n 和 a+ n + n , b +n + n分别并起来

然后出现了a吃b我就将 a ,b + n ,和 a + n , b +n + n ,还有 a +n + n , b分别并起来，后面只要出现了冲突的地方就表示是假话，

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e7 + 7;
const int INF = 0x3f3f3f3f;

int fa[N];

int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x , int y){
    fa[find(x)] = find(y);
}

int main(void){
    int n , k ;
    cin>>n>>k;
    int ans = 0;
    for(int i = 1 ; i <= 3 * n ; ++i){
        fa[i] = i;
    }

    for(int i = 1 ; i <= k ; ++i){
        int d , x , y;
        cin>>d>>x>>y;
        if(x > n || y > n){
            ans++;
            continue;
        }
        if(d == 1){
            if(find(x) == find(y + n) || find(x) == find(y + n + n)){
                ans++;
                continue;
            }
            merge(x , y);
            merge(x + n , y + n);
            merge(x + n + n , y + n + n);
        }
        else{
            if(find(x) == find(y) || find(x) == find(y + n + n)){
                ans++;
                continue;
            }
            merge(x , y + n);
            merge(x + n , y + n + n);
            merge(x + n + n , y);
        }
    }
    cout<<ans<<endl;
    return 0;
}  

带权并查集

struct node
{
    int par;                     //p[i].par表示节点i的父节点
    int relation;                   //p[i].relation表示节点i与其父节点(即p[i].par)的关系
}fa[N];

0表示和根节点是同一类

1表示被根节点吃

2表示吃根节点

初始话的时候relation就初始化为0，因为一开始fa[i]=i，此时相当于他的父节点就是他自己，即为同类

void init(int n)
{
    int i;
    for(i = 1;i <= n; ++i)
    {
        p[i].par = i;            //初始时集合编号就设置为自身
        p[i].relation = 0;        //因为p[i].par=i,即节点i的父亲节点就是自身,所以此时节点i与其父亲节点的关系为同类(即p[i].relation=0)
    }
}

接下来就是合并操作了
首先知道的是，在原来的并查集操作中，会将节点与节点的父节点的父节点连接起来，从而起到直接查询是否是同一个根节点的操作，那么这这里，我们进行合并的时候，就要意识到(x表示当前节点，xroot表示x的父节点，xxroot表示父节点的父节点)和父节点的关系的变化，比如xroot和xxroot为同类，而xroot和x是吃的关系，那么和xxroot的关系也应该是被吃的关系

即我们的关系的更新，这里我们需要用到向量的思维。

在合并操作之后，如果两个节点的根节点为同一个，并且他们们和根节点的关系相同（和根节点为同类或者都被根节点吃或者都吃根节点）那么他们也是同类

那么如果节点a吃根节点而根节点吃b，那么b就吃a，或者a和根节点为同类，根节点吃b，那么a也吃b

那么我们就把这2个元素之间的关系量转化为一个偏移量

x->y 偏移量0时 x和y同类 （即同吃或同被吃或同类

x->y 偏移量1时 x被y吃 （即x吃根 根吃y

x->y 偏移量2时 x吃y（即x和根为同类，根吃y

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

#define N 50010

struct node
{
    int pre;
    int relation;
};
node p[N];

int find(int x) //查找根结点
{
    int temp;
    if(x == p[x].pre)
        return x;
    temp = p[x].pre; //路径压缩
    p[x].pre = find(temp);
    p[x].relation = (p[x].relation + p[temp].relation) % 3; //关系域更新
    return p[x].pre; //根结点
}

int main()
{
    int n, k;
    int ope, a, b;
    int root1, root2;
    int sum = 0; //假话数量
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) //初始化
    {
        p[i].pre = i;
        p[i].relation = 0;
    }
    for(int i = 1; i <= k; ++i)
    {
        scanf("%d%d%d", &ope, &a, &b);
        if(a > n || b > n) //条件2
        {
            sum++;
            continue;
        }
        if(ope == 2 && a == b) //条件3
        {
            sum++;
            continue;
        }
        root1 = find(a);
        root2 = find(b);
        if(root1 != root2) // 合并
        {
            p[root2].pre = root1;
            p[root2].relation = (3 + (ope - 1) +p[a].relation - p[b].relation) % 3;
        }
        else //验证是否和题目给出的关系一致
        {
            if(ope == 1 && p[a].relation != p[b].relation)
            {
                sum++;
                continue;
            }
            if(ope == 2 && ((3 - p[a].relation + p[b].relation) % 3 != ope - 1))
            {
                sum++;
                continue;}
        }
    }
    printf("%d\n", sum);
    return 0;
}