种类并查集学习笔记

目录：

• 简介
• 例题简析

一、简介

普通的并查集只能维护联通性，即朋友的朋友是朋友；但当我们要维护对立性的时候，即敌人的敌人是敌人，就需要种类并查集了。

种类并查集指将元素分为两个并查集，若是联通的，即两者是朋友，我们就将其放入同一个并查集中；若是对立的，即两者是敌人，我们就将其放入两个不同的并查集中。

但这时我们并不知道这两个元素应该属于A群系还是B群系，故我们在放入之前先判断一下。一开始放入哪个群系都没有关系，但在第二次合并的时候，就应该判断一下，若是朋友，就将其放入同一个并查集中；若是敌人，就将其放入不同的并查集中。

二、例题简析

1. 三元种类并查集（P2024 [NOI2001]食物链）

   Description:

   给定 \(n\) 个元素，有以下两种关系：

   • \(x\sim y\) （即表示x和y是同类）
   • \(x\rightarrow y\) （即表示x吃y）

   再给定 \(m\) 条语句，确定 \(n\) 个元素的关系，判断语句真假。

   Mothod:

   显然，我们可以发现，在x与y两个元素之间有三种关系：

   1. \(x \sim y\)
   2. $ x\rightarrow y$
   3. \(x \leftarrow y\)

   此时用上面介绍的二元种类并查集显然是不能实现的，因为这种并查集两种元素之间只有两种关系：联通与对立。

   但不能使用二元种类并查集，我们可以使用三元并查集啊。此时我们就将所有元素分为三个并查集，A群系表示最高级动物，B群系表示中间级动物，C群系表示最低级动物。此时恒有 \(A \rightarrow B\)，\(B\rightarrow C\)。

   那么如何合并元素呢？

   若是 $ x\sim y$ ，但我们不知道x和y到底属于哪个群系， 那么我们就将A,B,C群系中的每一个x与y都连接在一起。即 \(x_A\eqcirc y_A\) , \(x_B \eqcirc y_B\) , \(x_C \eqcirc y_C\) ( \(x_C\) 表示 \(x\in C\) , $\eqcirc $ 表示将左右两边的元素合并)。

   若是 \(x\rightarrow y\) ，我们同样不知道x和y到底属于那个群系，于是我们就按照先前定义的，群系A中的x与群系B中的y合并，另两者相似。即 \(x_A \eqcirc y_B\) , \(x_B \eqcirc y_C\) , $ x_C \eqcirc y_A$ 。

   有如何判断语句真假呢？首先可以确定一点，我们判断该语句为真很困难，即从正面判断很困难，正难则反，我们从反面来考虑。

   若是语句 \(x\sim y\) ，我们从反面判断，即判断是否是 \(x\rightarrow y\) 或者 \(x\leftarrow y\) 。即判断 \(x_A \eqcirc y_B\) 或者 \(y_A \eqcirc x_B\) 。

   若是语句 \(x \rightarrow y\) ，我们就判断是否是 \(x \sim y\) 或者 \(x\leftarrow y\) 。即判断 \(x_A \eqcirc y_A\) 或者 \(y_A \eqcirc x_B\) 。

   最后就是简单的模板题了。

种类并查集学习笔记

原文：https://www.cnblogs.com/nth-element/p/12187238.html