并查集.txt

浙大ACM编程竞赛的摸板(内部质料),吐血奉献!!!!里面内容超多,把ACM题目分成了好几类,没一个类型都有详细的代码

//带路径压缩的并查集,用于动态维护查询等价类
//图论算法中动态判点集连通常用
//维护和查询复杂度略大于O(1)
//集合元素取值1..MAXN-1(注意0不能用!),默认不等价
#include <string.h>
#define MAXN 100000
#define _ufind_run(x) for(;p[t=x];x=p[x],p[t]=(p[x]?p[x]:x))
#define _run_both _ufind_run(i);_ufind_run(j)

struct ufind{
	int p[MAXN],t;
	void init(){memset(p,0,sizeof(p));}
	void set_friend(int i,int j){_run_both;p[i]=(i==j?0:j);}
	int is_friend(int i,int j){_run_both;return i==j&&i;}
};