当前位置: 代码迷 >> 综合 >> 【并查集路径压缩 模板】
  详细解决方案

【并查集路径压缩 模板】

热度:71   发布时间:2024-01-18 01:43:40.0

查找根节点:

void init(int n)  //初始化,将所有的点的父节点都初始化成其本身
{for (int i = 0; i <= n; i++)par[i] = i;
}//压缩和不压缩的都要知道,后边有时会处理不压缩的; 
int find(int x)   //找一个点的根结点 
{
1.	if ( x!= par[x])return /* par[x]=*/find(par[x]);return x;2.	return x == par[x] ? x : /*par[x]=*/find(par[x]);3.	while (x != par[x])x = par[x];//这三种都是朴素的查找,适合数据量不大的情况 
}

路径压缩:

	int q=x;while (par[q] != x){int j = par[q];par[q] = x;q = j;}这一种采取路径压缩的方法查找元素 ,防止溢栈 return par[x];	//别忘了return

合并:

void unite(int a, int b)  //合并 
{int fa = find(a);int fb = find(b);if (fa != fb)     //如果两个点的根节点不一样的话,就将其中一个接到另一个上面,使其成为一个集合par[fa] = fb;
}



  相关解决方案