奇偶游戏的另一个解法

带权并查集的主要思想是得到与根节点的关系, 然后就可以得到任意一点之间的关系, 这种关系需要自己想办法去维护。

而另一种思路, 扩展域的方法中, 集合内不再是一个点, 而是一种条件。如 $y是偶数$ 这样一个条件, 而在一个集合内的条件其之间必然是相互成立。

因此对于奇偶游戏一题, 可以定义 $x$ 为 x 是偶数, $x+n$ 定义为 x 是奇数。那么对于 $x,y$ 同类这个操作就可以被翻译为：

• 如果存在 $x+n$ 与 $y$ 在同一集合内, 则不成立
• 合并 $x+n$ 与 $y+n$, 合并 $x,y$ 不同类时：
• 如果存在 $x$ 与 $y$ 在同一集合内, 则不成立
• 合并 $x+n$ 与 $y$, 合并 $x$ 与 $y+n$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
using namespace std;
const int N = 5e4 + 10, base = N / 2;
unordered_map<int,int> S;
int f[N], n;
 
int find(int x) {
    if(x != f[x]) f[x] = find(f[x]);
    return f[x];
}
 
int get(int x)
{
    if(S.count(x) == 0) S[x] = ++n;
    return S[x];
}
 
int main()
{
    int m, res = 0;
    cin >> m;
    
    for(int i = 1; i < N ;i ++) f[i] = i;
    cin >> m;
    res = m;
    for(int i = 1; i <= m;i ++)
    {
        int a,b;
        string type;
        
        cin >> a >> b >> type;
        a = get(a - 1), b = get(b);
        
        if(type == "even")
        {
            if(find(a + base) == find(b))
            {
                res = i - 1;
                break;
            }
            f[find(a)] = find(b);
            f[find(a + base)] = find(b +base);
        }
        else {
            if(find(a) == find(b))
            {
                res = i - 1;
                break;
            }
            f[find(a + base)] = find(b);
            f[find(a)] = find(b + base);
        }
    }
    
    cout << res << endl;
    return 0;
}