什么是种类并查集

在某一集合中，不同个体之间存在着不同的关系，我们将同一类个体作为一个并查集，不同并查集之间的关系即为不同并查集个体之间的关系，这样的并查集称为种类并查集。

以例题说明

例题1：

洛谷P1525关押罪犯 一共有n个罪犯，m对罪犯之间有矛盾，矛盾的对立的，所以矛盾可以作为不同并查集之间的关系，这里则需要两种并查集。

同一并查集内的罪犯之间没有矛盾，不同并查集之间的任意两个罪犯都有矛盾，如果我们将矛盾按大到小排序，每次安排矛盾最大的一对放入两个并查集，如果安排不了了，则当前安排的这一对罪犯的矛盾即为可能实现的最小矛盾。

我们两个并查集可以为1-n，n+1-2n这样两倍大小的并查集，则实现了不同种类的并查集。

如何安排两个有矛盾的罪犯呢，我们可以认为，敌人的敌人就是朋友 则 merge(x, y+n); merge(y, x+n);

最后特判一下所有罪犯都能不发生矛盾的情况，即为0

完整代码：

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int MAXN = 2e5 + 7; struct node { int x, y, c; }a[MAXN]; int pre[MAXN]; int n, m; void init() { for(int i = 1; i <= 2 * n; i++) // 记得并查集初始化两倍大小 pre[i] = i; } bool cmp(node a, node b) { return a.c > b.c; } int find(int x) { if(pre[x] == x) return pre[x]; else return pre[x] = find(pre[x]); } void merge(int a, int b) { int x = find(a); int y = find(b); if(x != y) { pre[y] = x; } return ; } int main() { cin >> n >> m; init(); for(int i = 1; i <= m; i++) scanf("%d%d%d",&a[i].x, &a[i].y, &a[i].c); sort(a+1, a+1+m, cmp); int flag = 0; for(int i = 1; i <= m; i++) { int x = a[i].x; int y = a[i].y; int c = a[i].c; if(find(x) == find(y)) // 两个罪犯在一个并查集之中 不可调和 { cout << c << endl; return 0; } merge(x, y+n); // 敌人的敌人是朋友 merge(y, x+n); } cout << 0 << endl; // 特判 return 0; }

例题2：

POJ食物链

这里有三种动物，按照上面的思路，我们开三倍大小的并查集即可，我们认为 x+n吃x，x+2n吃x+n， x吃x+2n；y同理

我们在每次并入之前加上一个判断

如果是谎话就

ans++; continue;

如果不是则合并

如果是同类 merge(x, y); merge(x+n, y+n); merge(x+2n, y+2n);

如果x吃y则 merge(x+n, y); merge(x+2n, y+n); merge(x, y+2n);

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int MAXN = 3e5 + 7; int pre[MAXN]; int n, m; void init() { for(int i = 1; i <= 3 * n; i++) pre[i] = i; } inline int read() // { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int find(int x) { if(pre[x] == x) return pre[x]; else return pre[x] = find(pre[x]); } void merge(int a, int b) { int x = find(a); int y = find(b); if(x != y) { pre[y] = x; } return ; } int main() { cin >> n >> m; init(); int d, x, y; int ans = 0; for(int i = 1; i <= m; i++) { d = read(); x = read(); y = read(); if(x > n || y > n || (d == 2 && x == y)) { ans ++; continue; } if(d == 1) { if(find(x) == find(y+n) || find(y) == find(x+n)) { ans ++; continue; } merge(x, y); merge(x+n, y+n); merge(x+2*n, y+2*n); } else { if(find(x) == find(y) || find(x) == find(y+n)) { ans++; continue; } merge(x+n, y); merge(x+2*n, y+n); merge(x, y+2*n); } } cout << ans << endl; return 0; }

最后留一个练习题 POJ2492（十分easy）