并查集

发表于 更新于 分类于 阅读次数：

  好吧，前两天做了一场CF，遇到一道并查集的题目，感觉并查集还需学习啊，记录一下 具体的算法如下

  1. 有father数组，全部初始化为本身
  2. 添加一个关系进来的时候，s–t，找到s的祖先a,t的祖先b，将a的father设为b
  3. 通过查找祖先，来确定是否在一个集合内
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void init(int n){//初始化，节点编号1-n
    for (int i=1;i<=n;i++) father[i]=i;
}

int find(int x)//查找祖先节点
{
	while (father[x]!=x) x=father[x];
	return x;
}

void add(int s,int t)//增加一个关系，改变集合
{
  int a=find(s);
  int b=find(t);
  father[a]=b;
}

bool judge(int s,int t)//判断是不是一个集合
{
    return find(s)==find(t);
}