데이터 구조 와 알고리즘 - 집합 배열 실현

병 찰 집
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));
}