[数据结构与算法]3期集训第一天

今天学了一下种类并查集，它是在并查集的基础上做了一些改变的数据结构，并查集是维护的一种传递的关系比如亲戚的亲戚还是亲戚而种类并查集一般维护的关系是敌人是敌人是朋友的关系，储存节点之间的关系一般开维护数量两倍的大小。
然后做了一道种类并查集的列题代码如下。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100001;
int f[40001];
struct node{
	int a,b,w;
}d[N];
int find(int x){
	if(f[x]!=x){
		f[x]=find(f[x]);
	}
	return f[x];
}
bool cmp(node a,node b){
	return a.w>b.w;
}
void merge(int a,int b){
	int x=find(a),y=find(b);
	if(x!=y){
		f[y]=x;
	}
}
bool g(int a,int b){
	if(find(a)==find(b)) return true;
	return false;
}
int main(){
	int m,n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2*n;i++){
		f[i]=i;
	}
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].w); 
	} 
	sort(d,d+m,cmp);
	for(int i=0;i<m;i++){
		if(g(d[i].a,d[i].b)){
			printf("%d",d[i].w);
			break;
		}
		merge(d[i].a,d[i].b+n);
		merge(d[i].b,d[i].a+n);
		if(i==m-1){
			printf("0");
		}
	}
	return 0;
}