模板 - 数据结构

链表

定义

struct Peter{
	int val;
	int nxt,pre;
}node[M];
int idx=0;

初始化

inline void Init() // head:0; tail:n+1
{
	node[0]={0,n+1,0};
	node[n+1]={0,n+1,0};
	return;
}

在 p 后插入 val

inline void insert(int p,int val)
{
	node[++idx]={val,node[p].nxt,p};
	node[node[p].pre].pre=idx,node[p].nxt=idx;
	return;
}

删除 p

inline void remove(int p)
{
	node[node[p].nxt].pre=node[p].pre;
	node[node[p].pre].nxt=node[p].nxt;
	return;
}

并查集

定义 & 初始化

int fa[N];
void uInit()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	return;
}

查询

int uask(int x)
{
	if(fa[x]==x) return fa[x];
	else return fa[x]=uask(fa[x]);
}

合并

void merge(int x,int y)
{
	fa[ask(y)]=ask(x);
	return;
}