数据结构与算法——并查集数组实现

并查集

在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

主要涉及操作： 初始化 把每个点所在集合初始化为其自身。 通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。 查找 查找元素所在的集合，即根节点。 合并 将两个元素所在的集合合并为一个集合。 通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

数组实现模板

下面用C++利用数组进行并查集实现：

//UnionFind.h
#pragma once
#define parent_max 1024
using namespace std;

struct Element
{
          
   
	int val;
	Element() {
          
   }
	Element(int va) :val(va) {
          
   }
};

class UnionFind
{
          
   
public:
	UnionFind();
	UnionFind(int arr[], int len);
	//UnionFind(int arr[], int len,int w);
	~UnionFind();

	int findHead(int element);
	void unionSet(int element1, int element2);
	bool isSameset(int element1, int element2);

private:
	int parent[parent_max];	//用于存放第i个元素的父节点
};

//UnionFind.cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
#include "UnionFind.h"
using namespace std;
UnionFind::UnionFind(){
          
   }
UnionFind::~UnionFind(){
          
   }
UnionFind::UnionFind(int arr[], int len)
{
          
   
	//将数组中每个元素均加入并查集，自己是自己的父，也就是自己成集合
	for (int i = 0; i < len; i++)
	{
          
   
		parent[arr[i]] = arr[i];
	}
}
int UnionFind::findHead(int element)
{
          
   
	int son = element;
	int temp = 0;
	//当element不等于他的parent，继续往找，直到他的parent
	while (element != parent[element])	
	{
          
   
		element = parent[element];
	}
	//优化：扁平化，沿途所有的element全部直接指向他的parent
	while (son != element)	
	{
          
   
		temp = parent[son];
		parent[son] = element;
		son = temp;
	}
	return element;
}
void UnionFind::unionSet(int element1, int element2)
{
          
   
	//分别找到头，头相同不操作，头不同合并集合
	int e1 = findHead(element1);
	int e2 = findHead(element2);
	if (e1 == e2)
		return;
	else
		parent[e1] = parent[e2];
}

bool UnionFind::isSameset(int element1, int element2)
{
          
   
	//头相同，则一定在同一个集合
	return (findHead(element1) == findHead(element2));
}