POJ 1182 - 食物链

带权并查集

动物王国中有三类动物A，B，C，构成环形：A吃B，B吃C，C吃A。

现有N个动物，从1开始编号，每个动物都是A，B，C中的一种，但我们并不知道是哪一种。

用两种说法描述这N个动物的食物链关系：

• 1 X Y 表示X和Y是同类
• 2 X Y 表示X吃Y

给出K句话，有些是真的，有些是假的，满足下列任一条件即为假话，否则是真话：

• 当前的话与之前的某些真话冲突
• 当前的话中X或Y比N大
• 当前的话表示X吃X

输出假话的总数。

分析

这个题目是有关系的集合问题，可以利用带权并查集解决。

定义两个数组fa和rank，fa用来判断集合关系，rank用来描述其与根节点的关系。因为关系满足传递性，所以可以推导出给出条件下的当前关系，在判断与之前已有关系是否矛盾。

本题的解法巧妙地利用了模运算，rank数组用0表示同类，1表示当前点能吃根，2表示当前点被根吃。

传递性推导

结点A与根关系	结点B与根关系	A与B关系
0	0	0
0	1	2
0	2	1
1	0	1
1	1	0
1	2	2
2	0	2
2	1	1
2	2	0

首先用rank标记当前点与根的关系，然后利用传递性，得到任意两点的关系(rank[a] - rank[b]) % 3。



结点A与根关系	结点B与A关系	B与根关系
0	0	0
0	1	1
0	2	2
1	0	1
1	1	2
1	2	0
2	0	2
2	1	0
2	2	1

并且利用路径压缩维护这种关系，rank[b] = (rank[b] + rank[a]) % 3，通过当前点到之前根的关系，加上之前根到当前根的关系，维护当前点到根的关系。



每次添加新关系时，导致两个集合的连接，可以通过当前点的关系，反推出两个根的关系：rank[rb] = rank[a] - rank[b] + relation(b->a)

本题需要注意的是传入的relation恰为描述的种类号减一。



代码

#include <iostream>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;

const int MAXN = 100005;
const int INF = 0x3F3F3F3F;
const double eps = 1e-6;
const int MOD = 1e9 + 7;

int fa[MAXN], _rank[MAXN];
int n, k, ans;

void init(int n)
{
    for(int i = 0; i <= n; i++)
    {
        fa[i] = i;
        _rank[i] = 0;
    }

    ans = 0;
}

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
    {
        int temp = fa[x];
        fa[x] = find(fa[x]);
        _rank[x] = (_rank[x] + _rank[temp]) % 3;
        return fa[x];
    }
}

void merge(int r, int u, int v)
{
    int fu = find(u);
    int fv = find(v);

    if(fu != fv)
    {
        fa[fu] = fv;
        _rank[fu] = (_rank[v] - _rank[u] + r + 3) % 3;
    }
}

bool check(int r, int u, int v)
{
    if(u > n || v > n)
        return false;
    if(r == 1 && u == v) // 传入的序号已减一
        return false;

    int fu = find(u);
    int fv = find(v);

    if(fu == fv)
        return ((_rank[u] - _rank[v]) % 3 + 3 ) % 3 == r;
    else return true;    
}

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

    init(n);

    int a, b, c;

    for(int i = 0; i < k; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a --;
        if(check(a, b, c))
            merge(a, b, c);
        else
            ans ++;
    }

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

    return 0;
}