题解：P7304 [COCI2018-2019#1] Zamjena

一道并查集的题目，实现的时候细节较多。

【注：以下 fa 与 num 数组的 $1 \sim n$ 存第一个数组， $n + 1 \sim 2n$ 存第二个数组。】
因为与字符有关系，所以可以用 map 来记录每一个变量/数字所出现的第一个位置并标记 fa[i] = i。

1 2	if (num[a[i]] != 0) fa[i] = num[a[i]]; else fa[i] = num[a[i]] = i;

接下来就要以 $O(n)$ 的时间复杂度依次判断每个数组的第 $i$ 位是否符合要求了。这里需要进行分类讨论，有以下几种情况 (设两个数组分别为 a 与 b，find (int x) 为找到 $x$ 的父亲)：

$a_i$ 与 $b_i$ 均为常量直接比较是否相等即可
$a_i$ 为常量， $b_i$ 为变量
2.1. $b_i$ 的值已经确定比较是否相等
2.2. $b_i$ 的值未确定 fa[find (b[i])) = find (a[i])
$a_i$ 为变量， $b_i$ 为常量
3.1. $a_i$ 的值已经确定比较是否相等
3.2. $a_i$ 的值未确定 fa[find (a[i])) = find (b[i])
$a_i$ 与 $b_i$ 均为变量
4.1. $a_i$ 与 $b_i$ 均已经确定比较是否相等
4.2. 只有 $a_i$ 已经确定 fa[find (b[i])) = find (a[i])
4.3. 只有 $b_i$ 已经确定 fa[find (a[i])) = find (b[i])
4.4. $a_i$ 与 $b_i$ 均未确定随便选一个作为父亲，进行合并

于是就有代码：

bool correct (int x)
{
    //bool isnumber[MAX << 1],isok[MAX << 1];//是否是数字；是否已确定 
    int dx = find (num[a[x]]),dy = find (num[b[x]]);
    if (isnumber[x] && isnumber[x + n])
    {
        if (a[x] != b[x]) return 0;
        else return 1;
    }
    else if (isnumber[x])
    {
        if (dx == dy) {isok[dx] = 1;return 1;} 
        else if (!isok[dy]) fa[dy] = dx,isok[dy] = 1;
        else return 0;
    }
    else if (isnumber[x + n])
    {
        if (dx == dy) {isok[dx] = 1;return 1;}
        else if (!isok[dx]) fa[dx] = dy,isok[dx] = 1;
        else return 0;
    }
    else
    {
        if (!isok[dx] && !isok[dy]) fa[dx] = dy;
        else if (!isok[dx]) fa[dx] = dy,isok[dx] = 1;
        else if (!isok[dy]) fa[dy] = dx,isok[dy] = 1;
        else if (dx != dy) return 0;  
    }
    return 1;
}

最后若所有返回值都是 1，则符合题意；否则就是不符合。