先说说种类并查集吧。
种类并查集是并查集的一种。但是，种类并查集中的数据是分若干类的。具体属于哪一类，有多少类，都要视具体情况而定。当然属于哪一类，要再开一个数组来储存。所以，种类并查集一般有两个数组，一个存并查集内的父子关系，一个存各个节点所属的种类关系。
以这道题为例（题意在后面，如果没有读题，可以先看完题在来看这部分）——
这道题很明显，将bug分成两类，一公一母。但是实际上我们并不关心它是公的还是母的，只关心它们之间是同性还是异性。所以，我们可以设与并查集的根节点同性的为0，反之为1。所以，我们就需要在int mfind(int x)里加上一个对于种类进行的操作。这个操作需要不停地修改每个bug所属的种类。
需要反复修改的理由：每次合并，我们都会将两个集合合并成一个集合，此时就会有一个根节点变成普通节点。那么之前在这个根节点之后的节点所拥有的关系就需要修改。前面已经说了，我们设置的01关系是和根节点相关的关系，那么当根节点变化的时候，我们的对应关系就需要变化。
值得注意的是，这个修改并不需要立刻进行，对于消失的那个根节点上的子节点，只需要在下次查询的时候进行就可以（类似于离线操作。有些人的代码在进行合并之后就进行了一次查找，目的就是马上将查找的节点的种族及时修改，个人认为这是没有必要的）。但是对于消失的那个根节点，我们则需要及时将它与仍然存在的根节点的关系及时修改，因为这里是首次合并时进行的种类关系确定，即，将单个节点合并成一个集合时进行的种类关系确定。
种类关系的确定所使用的运算十分巧妙，我只是大概明白，却还不是完全清楚。种族关系确定时，如果两者的种族相同，那么需要修改其中一方的种族，如果两者的种族不同，那么保持不变。当然，这是这道题的操作，不同的题目会有不同的要求。
题意——
有两种bug，一种是公的，一种是母的。
现在给他们配对，只能公配母，否则就会出bug了，问你他所提出的配对方式有没有bug。
输入——
第一行一个整数t，表示有t组数据。
接下来，每组数据第一行有两个整数n, m，表示共有n个虫子，m种配对。
接下来m行，每行两个整数a, b，表示一种配对。
输出——
输出是第几组数据
输出是否存在bug。
数据举例——
1
3 3
1 2
1 3
2 3
这里表示共有1组数据，这组数据包含3只bug和3种配对。
由于1可以与2配，1可以与3配，那么2, 3同性……所以这一组是个bug（这里不存在gay和百合……）
上代码——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int M = ; int fm[M];
int n, m, t;
bool tp[M], flag; //tp[]记录种族，flag记录是否存在bug int mfind(int x) //查询操作
{
if(fm[x] == x) return x;
int fx = fm[x];
fm[x] = mfind(fm[x]);
tp[x] = tp[fx]^tp[x]; //修改种族，对查询的子节点进行
return fm[x];
} void mmerge(int x, int y)
{
int fx = mfind(x);
int fy = mfind(y);
//printf("%5d%5d\n", fx, fy);
if(fx != fy) //合并操作
{
fm[fy] = fx;
tp[fy] = tp[x]^tp[y]^; //修改种族，对消失的根节点进行
}
else if(tp[x] == tp[y]) flag = ; //如果两个节点属于同一并查集且种族相同，则出现bug
} void init() //各种数据初始化
{
memset(tp, , sizeof(tp)); //种类初始化，所有节点都和自己属于同一种类
flag = ; //目前没有bug
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) fm[i] = i; //并查集初始化，这个不用多说了吧
} void work()
{
for(int i = ; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
if(!flag) mmerge(a, b); //不存在bug才进行并查集操作，
}
} void output(int tm)
{
printf("Scenario #%d:\n", tm);
if(!flag) printf("No suspicious bugs found!\n");
else printf("Suspicious bugs found!\n");
//for(int i = 1; i <= n; i++) printf("%5d", tp[i]);
//printf("\n");
printf("\n");
} int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
init();
work();
output(tm);
}
return ;
}
当然，这个代码里我使用的是抑或^符号来处理的，主要原因是这里一共只有两个种类（使用bool数组进行记录也是如此的原因），如果种类比较多，就需要使用%符号或者其他的方式处理了。
ps：我也是一边写博客一边思考的，在写完的时候对于这个算法的思路确实又清晰了不少，看来写博客还是很有用处的。