总算理解种类并查集了，浅说一下吧。
有大佬已经讲得很清楚了，戳这 -> 作者:OIer某罗。
先看[NOIP2010 提高组] 关押罪犯这题。
我就再讲讲理解：
种类并查集像分类讨论，比如这题，我们考虑的是：
原本所有罪犯都在 \(A\) 监狱，一个一个扔到 \(B\) 监狱。
但不能决定谁到 \(B\) 监狱去，所以用种类并查集分类讨论，找到最坏的无法避免的冲突。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4+5, M = 2e5+5;
int n,m,fa[N<<1];
//1~n 表示A监狱 n+1~2*n 表示B监狱
struct ss{
int u,v,w;
}a[M];
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
return s*f;
}
bool cmp(ss a,ss b){
return a.w>b.w;
}
inline int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void unite(int x,int y){
x=find(x);y=find(y);
if(x==y)return;
fa[x]=y;
}
/*
wrong-solution:
原本所有人都在A监狱，一个一个扔到B监狱，
但两个人不能决定谁去B,出问题了。
real-solution:
用种类并查集，一个人在数组中对应2位置，在A监狱位置和在B的位置
记录关系的话开两倍大小，一种 1号去A,2号去B ;一种 2号去A,1号去B
问题就解决了。
*/
int main(){
cin>>n>>m;
for(int i=0;i<=n<<1;i++)fa[i]=i;
for(int i=1;i<=m;i++)a[i].u=read(),a[i].v=read(),a[i].w=read();
sort(a+1,a+m+1,cmp);//贪心
for(int i=1;i<=m+1;i++){//到m+1就可以不用特判0的情况，因为a[m+1].u a[m+1].v a[m+1].w 都是0
int u=a[i].u,v=a[i].v;
if(find(u)==find(v)||find(u+n)==find(v+n)){cout<<a[i].w;break;}
//已经在同一个监狱就不分类讨论了，都已经打起来了
unite(u,v+n);unite(u+n,v);
//分类讨论，一个到A监狱，一个到B监狱
}
return 0;
}