POJ-1182 食物链（带权并查集或基础并查集空间倍增）

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

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

int n = 150005;
vector<int> parent(n);
vector<int> rankNum(n); //树的高度
//int parent[150005];
//int rankNum[150005];

//初始化
void init(int num)
{
    // int len = parent.size();
    // if (n > len) {
    //  parent.resize(n + 1);
    //  rankNum.resize(n + 1);
    // }

    for (int i = 0; i <= num; ++i) {
        parent[i] = i;
    }
}

//查询操作
int find(int x)
{
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

//合并x和y所属的集合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    //如果x和y所属的集合相同，无需操作
    if (x == y) return;
    //按高度合并
    if (rankNum[x] < rankNum[y]) parent[x] = y;
    else {
        parent[y] = x;
        if (rankNum[x] == rankNum[y]) ++rankNum[x];
    }
}

//查询x和y是否属于同一个集合
bool isSame(int x, int y)
{
    return find(x) == find(y);
}

int main()
{
    // std::ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    int N, K;
    cin >> N >> K;
    init(N * 3);

    int cnt = 0;
    while (K--) {
        int seq, x, y;
        //cin >> seq >> x >> y;
        scanf("%d%d%d", &seq, &x, &y);

        //输入数据存在错误
        if (x < 0 || y < 0 || x > N || y > N) {
            ++cnt;
            continue;
        }
        //判断每个断言是否正确
        if (seq == 1) {
            //x和y是同类，所以不能互吃
            if (isSame(x, y + N) || isSame(x, y + 2 * N)) ++cnt;
            else {
                unite(x, y);
                unite(x + N, y + N);
                unite(x + 2 * N, y + 2 * N);
            }
        }
        else { //捕食关系
            //捕食关系不能是同类或捕食关系反过来
            if (isSame(x, y) || isSame(y, x + N)) ++cnt;
            else {
                unite(x, y + N);
                unite(x + N, y + 2 * N);
                unite(x + 2 * N, y);
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

又是评测系统挖坑的题目，这一次问题不是出在对于标准库的支持上了，而是出现在输入输出上。按照以往，使用cin, cout关掉同步即可，但是这个题目关掉也会TLE，只能用scanf。

第一种方法是使用基础并查集，空间翻倍的方法，和《挑战程序设计竞赛》里的方法是一致的，对于输入的x，那么x,x+N,x+2N分别代表属于ABC三类，所以总共可能出现9种对应关系，其中三种对应同一种类，三种对应x吃y，三种对应y吃x，当归为同一组的时候，对应的三组都要进行合并。

会发现在每种输入下只判断了两种情况，其实可以这么理解，比如输入是1 x y，即断言x和y属于同一类，但是没说明究竟属于ABC中的哪一个，所以与之对应的就是x吃y和y吃x的关系，之所以不需要把比如x吃y的三种情况:x，y+N; x + N, y+2n; x+2N, y都去判断是因为，如果在输入1 x y之前就有了x吃y的关系，那么上面三种情况必然已经合并过了，无论检验那种情况都可以得到x吃y的结论，所以只需要检查一个即可。y吃x的检验同理。

https://blog.csdn.net/yjr3426619/article/details/82315133 很不错的总结。

采用带权并查集：

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

int n = 50005;
vector<int> parent(n);
//vector<int> rankNum(n); //树的高度
vector<int> rela(n);

//初始化
void init(int num)
{
    // int len = parent.size();
    // if (n > len) {
    //  parent.resize(n + 1);
    //  rankNum.resize(n + 1);
    // }

    for (int i = 0; i <= num; ++i) {
        parent[i] = i;
    }
}

int find(int x)
{
    if (x == parent[x]) return x;
    else {
        int root = parent[x];
        parent[x] = find(parent[x]); //路径压缩
        rela[x] = (rela[x] + rela[root]) % 3;
        return parent[x];
    }
}

void unite(int x, int y, int r)
{
    int xRoot = find(x);
    int yRoot = find(y);

    if (xRoot == yRoot) return;

    parent[xRoot] = yRoot;
    rela[xRoot] = (rela[y] + r - rela[x] + 3) % 3;
}

bool solve(int seq, int x, int y)
{
    if (find(x) == find(y)) { //表明在当前输入之前已经可以得到x与y的关系
        int tmpRela = (rela[x] - rela[y] + 3) % 3;
        return tmpRela == seq;
    }

    return true;
}


int main()
{
    // std::ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    int N, K;
    cin >> N >> K;
    init(N);

    int cnt = 0;
    while (K--) {
        int seq, x, y;
        scanf("%d%d%d", &seq, &x, &y);
        //cin >> seq >> x >> y;
        //非法的输入
        if (x <= 0 || x > N || y <= 0 || y > N || (seq == 2 && x == y)) {
            ++cnt;
            continue;
        }
        --seq;
        if (solve(seq, x, y)) unite(x, y, seq);
        else ++cnt;
    }
    cout << cnt << endl;

    return 0;
}

从一个结点x指向另一个结点y，表明x和y有联系，相对关系用r来表示。0表示x和y是同类，1表示x吃y，2表示x被y吃。新开一个名为rela的数组，代表结点之间的关系（relation，不这么命名是因为会和标准库函数名冲突），设x所属的集合的根节点为xRoot，则rela[x]代表x对xRoot的关系。

查询操作。已知x和y存在相对关系，关系从y指向x，并且知道x和根节点xRoot的关系，那么当查询y的时候，按照路径压缩的要求，需要将y的根节点也设为xRoot，并且需要去更新y和根节点的关系，即rela[y]。关系是不会因为经过中间的一些结点（比如x）而改变，设y对x的关系为r，那么应有r + rela[x] = rela[y]。为了始终用0，1，2表示关系，需要对结果取模。那么关键问题来了，r是多少，其实在没有去改变y的根节点之前，y的根节点是x，所以会有原来的r = rela[y]，那么更新的时候需要变动两个：一个是修改根节点，和基础并查集一致，另一个就是修改关系，rela[y] = (rela[x] + rela[y]) % 3。

查询相对关系。如果已知x和y属于同一集合，那么可知x和y的根节点相同，现在想知道x对y的关系。根据图中关系可以得出：r + rela[y] = rela[x]，则r = rela[x] - rela[y]，为了防止r出现负数，那么r = (rela[x] - rela[y] + 3) % 3。

合并操作。现在已经知道x和y属于同一集合，现在需要对两个集合的根节点进行合并，假设是把x的根节点合并到y，修改parent的操作和基础并查集一致。从图中可以得到关系：r + rela[y] = rela[x] + rela[parent[x]]，显然需要更新的是rela[parent[x]]，为了防止出现负数，则有：rela[parent[x]] = (r+ rela[y] - rela[x] + 3) % 3