并查集(c++)

并查集簡介：在一些應用問題中，需要将n個不同的元素劃分為一組不相交的集合，在劃分過程中需要反複查詢某個元素歸屬于哪個集合。并查集就是一種适合于描述這類問題的抽象資料類型。

并查集主要支援的操作：

  1. merge(Root1, Root2) //并操作；

  2. get (x) //搜尋操作；

  3. UFS (s) //構造函數。

一般情形，并查集主要涉及兩種資料類型：集合名類型和集合元素的類型。

在許多情況下，可以用整數作為集合名。如果集合中有n個元素，可以用1到n之間的整數表示集合元素。

對于并查集來說，每個集合用一棵樹表示。

集合中每個元素的元素名分别存放在樹的結點中，此外，樹的每一個結點還有一個指向其雙親結點的指針。

根結點的父指針為負數，其絕對值表示集合中的元素個數。

// 并查集.cpp : 此檔案包含 "main" 函數。程式執行将在此處開始并結束。
//并查集的基本操作

#include "pch.h"
#include <iostream>
#include<vector>
using namespace std;
const int defaultSize = 10;

class UFS {
private:
	vector<int> parent;
public:
	UFS(int size = defaultSize) {
		//初始化:初始的時候每個結點各自為一個集合,
		//parent[i]表示結點 i 的父親結點,如果 parent[i]=i,我們認為這個結點是目前集合根結點。
		for (int i = 0; i < size; i++)
		{
			parent.push_back(i);
		}
	}
	int old_get(int x)//查找:查找結點所在集合的根結點,結點 x 的根結點必然也是其父親結點的根結點。
	{
		while (parent[x]!=x)
		{
			x = parent[x];
		}
		return x;
	}
	void merge(int x, int y)//将兩個節點所在的集合并起來，一般要首先檢查兩個節點是否屬于同一個集合
	{
		x = old_get(x);
		y = old_get(y);
		if (x != y)// 不在同一個集合
		{
			parent[y] = x;
		}
	}
	/*
	前面的并查集的複雜度實際上在有些極端情況會很慢.
	比如樹的結構正好是一條鍊，那麼最壞情況下，每次查詢的複雜度達到了O(n)。
	這并不是我們期望的結果。路徑壓縮的思想是，我們隻關心每個結點的父結點，而并不太關心樹的真正的結構。
	這樣我們在一次查詢的時候，
	可以把查詢路徑上的所有結點的father[i]都指派成為根結點。
	隻需要在我們之前的查詢函數上面進行很小的改動
	*/
	int get(int x)
	{
		if (parent[x] == x)
			return x;
		else
			return parent[x] = get(parent[x]);
	}
	/*
	路徑壓縮在實際應用中效率很高,
	其一次查詢複雜度平攤下來可以認為是一個常數。并且在實際應用中,我們基本都用帶路徑壓縮的并查集。
	*/
	
	};
class WUFS {
	/*
	所謂帶權并查集，是指結點存有權值資訊的并查集。并查集以森林的形式存在，
	而結點的權值，大多是記錄該結點與祖先關系的資訊。比如權值可以記錄該結點到根節點的距離。
	*/
	/*
	例題
	在排隊過程中，初始時，一人一列。一共有如下兩種操作。
	合并：令其中的兩個隊列 A，B 合并，也就是将隊列 A 排在隊列 B 的後面。
	查詢：詢問某個人在其所在隊列中排在第幾位。
	*/
	/*
	我們不妨設 size[]為集合中的元素個數，dist[]為元素到隊首的距離，
	*/
private:
	vector<int> parent;
	vector<int> size;
	vector<int> dis;
public:
	WUFS(int s)
	{
		for (int i = 0; i < s; i++)
		{
			parent.push_back(i);
			dis.push_back(0);
			size.push_back(1);
		}
	}
	int get(int x)
	{
		if (parent[x] == x)
			return x;
		int y = parent[x];
		parent[x] = get(y);//太巧妙了
		dis[x] += dis[y];
		return parent[x];
	}
	void merge(int x, int y)
	{
		x = get(x);
		y = get(y);
		if (x != y)
		{
			parent[x] = y;
			dis[x] = size[y];
			size[y] += size[x];
		}
	}
};
int main()
{
    std::cout << "Hello World!\n"; 
}