并查集扩展(friend_enemy).txt

对参加ACM竞赛非常有用的几个ACM答题模板（数论

//带路径压缩的并查集扩展形式
//用于动态维护查询friend-enemy型等价类
//维护和查询复杂度略大于O(1)
//集合元素取值1..MAXN-1(注意0不能用!),默认无关
#include <string.h>

#define MAXN 100000
#define sig(x) ((x)>0?1:-1)
#define abs(x) ((x)>0?(x):-(x))
#define _ufind_run(x) for(;p[t=abs(x)];x=sig(x)*p[abs(x)],p[t]=sig(p[t])*(p[abs(x)]?p[abs(x)]:abs(p[t])))
#define _run_both _ufind_run(i);_ufind_run(j)
#define _set_side(x) p[abs(i)]=sig(i)*(abs(i)==abs(j)?0:(x)*j)
#define _judge_side(x) (i==(x)*j&&i)

struct ufind{
	int p[MAXN],t;
	void init(){memset(p,0,sizeof(p));}
	int set_friend(int i,int j){_run_both;_set_side(1);return !_judge_side(-1);}
	int set_enemy(int i,int j){_run_both;_set_side(-1);return !_judge_side(1);}
	int is_friend(int i,int j){_run_both;return _judge_side(1);}
	int is_enemy(int i,int j){_run_both;return _judge_side(-1);}
};