Union Find

Disjoint Set Union (Union Find) өгөгдлийн бүтцийн тухай.

Нэрнээс нь харвал union буюу нэгтгэх find буюу хайх, disjoint буюу салангид гэсэн гурван үгээр энэхүү өгөгдлийн бүтэц нэрлэгджээ. Мэдээж энэхүү гурван гол ойлголтыг агуулсан байхнээ. Өөрөөр хэлбэл энэ нь

1. Find буюу ямар хэсэгт байгааг хайх үйлдлийг хийнэ
2. Union буюу салангид байгаа 2 хэсгийг нэгтгэх

гэсэн 2 гол үйлдэлтэй. Өөрөөр хэлбэл бидэнд анх салангид олон хэсгүүд байгаа ба түүнийг хэрхэн хялбар байдлаар нэгтгэх, тухайн элэмэнт аль хэсэгт байгааг олоход ашигладаг.

Бүтэц

Ямархуу бүтцээр энэхүү үйлдлүүдийг хялбар хийж болох вэ? Өөрөөр хэлбэл тухайн нэг хэсэгт байгаа оройнуудыг бид ижил гээд R гэж тэмдэглэе. Тухайн хэсэгт шинэ 1 элэмэнт нэмэгдвэл бид тэрхүү элэмэнтийг мөн R гэж тэмдэглэхэд л хангалттай. Харин асуудал нь эхний хэсэгт X элэмэнт дараагийн хэсэгт Y элэмэнт байгаа ба энэхүү хоёр хэсгийг нийлүүлэх үйлдлийг хэдэн үйлдлээр хийх вэ? min(X, Y) үйлдлээр хийж болох ба бага элемэнттэй хэсгийн бүх элэмэнтийг их хэсгийн утгаар онооход болно. Заа тэгхээр эхний бүтэц маань

1. Find - буюу хайхад 1 үйлдэл хийнэ
2. Merge - буюу 2 хэсгийг нийлүүлэхэд хоёр хэсгийн жижиг элемэнтийн тоотой адил үйлдэл хийнэ

Гэхдээ тухайн салангид байх 2 хэсэг нь их хэмжээний элэмэнттэй бол энэ нь удах нь тодорхой. Илүү ашигтай бүтэц бидэнд хэрэгтэй. Тэгвэл бид мод(tree) бүтцээр хадгалж болно. Мод нь цикл агуулаагүй холбогдсон граф ба

• Тухайн салангид хэсгийн төлөөлөгч гэж 1 оройг сонгоно (root буюу язгуур гэдэг)
• Тухайн хэсгийн ямар ч орой нь өөрийн эцэг буюу parent-г заана
• Хамгийн дээд эцэг нь root буюу салангид хэсгийн төлөөлөгч байна

гэсэн байдлаар бид хадгаля. Тэгвэл merge буюу нэгтгэх үед

• X оройн язгуур буюу root-г олно. Ингэхдээ эцгээр нь дамжин явсаар очно
• Y оройн язгуур буюу root-г олно. Ингэхдээ эцгээр нь дамжин явсаар очно
• Merge хийхдээ X оройн төлөөлөгч буюу root оройг Y орой орсон хэсгийн төлөөлөгч буюу root оройн эцэг болгоно.

Үүний дараа Y орой орсон хэсгийн ямар ч оройн хувьд find буюу root-г олох үйлдлийг хийхэд X оройн эцгийг заана. Хугацааны үнэлгээний хувьд merge хийх нь find-хийх үйлдэл болж байна. Find буюу хайх нь хамгийн муудаа гинж хэлбэртэй байхад дээшээ орой болгоноор дамжаад очно. Үүнийг яаж хурдан болгох вэ? Бид хайх үед эцгээр дамжиж явж байгаа ба ингэх бүрдээ тухайн оройн шууд эцгийг root оройгоор сольж чадна. Өөрөөр хэлбэл би 1 удаа тухайн оройгоос root-г олох үйлдэл хийсний дараа тухайн замдах бүх орой нь үүний дараа root оройг шууд заасан байна.

4-р оройгоос хайх үйлдэл хийсний дараа

Энэхүү зурганд 4-р оройгоос хайх үйлдэл хийсний дараа ямархуу болж хувирсныг харуулж байна. Union find-нь бараг л 1 үйлдлээр хайх, нэгтгэх үйлдлийг хийж чаддаг.

Жишээ

Бидэнд анх аль ч хоёр орой нь хоорондоо холбогдоогүй граф байгаа гэж үзье. Өөрөөр хэлбэл нийт N ширхэг компонент байгаа. Нийт Q ширхэг холболт байгаа ба x, y гэсэн хоёр оройг холбох ба энэ бүх холболтын дараа нийт хэдэн ширхэг компонент байгааг олох жишээ бодлого бодоцгооё.

• par гэсэн array-д тухайн оройн эцгийг хадгална
• s гэсэн array-д тухайн орой эцэг байхад хэдэн хүүхэд доороо агуулж байгаа вэ гэсэн тоог хадгална
• find буюу хайх үйлдлийн хувьд recursive ашиглан олсон эцгээ замд таарсан оройнуудад онооно

// union find
#include <bits/stdc++.h>
ing namespace std;

const int N = 200000;	// тогтмол хувьсагч

	int n;		// оройн тоо
	int q;		// хүсэлтийн тоо
	int s[N];	// s[x] нь x гэсэн дээд эцэгтэй компонентийн хэмжээ
	int comp;	// нийт компонентийн тоо
	int par[N];	// par[x] нь x оройн эцгийг хадгална.

int find(int x) {		// x оройн дээд эцгийг олох функц
	if(x == par[x]) {	// x оройн эцэг өөрөө гэдэг нь хамгийн дээд орой мөн
		return x; 	// тиймээс x оройг буцаана.
	}
	// эсрэг тохиолдолд
	// par[x] оройн дээд эцэг нь x оройн дээд эцэг тул par[x] оройн 
	// дээд эцгийг олно.

	int root = find( par[x] ); 

	// root нь дээд эцэг бөгөөд 
	// x оройн эцгийг root гэж оноосноор холболтын урт багасна.
	// ингэснээр бидэнд ашигтай.

	par[x] = root;
	return root;
}

int main() {
	cin >> n;	// оройн тоо
	comp = n;	// n ширхэг компонент байгаа.

	for(int i = 1; i <= n; i++) {
		par[i] = i;	// i оройн эцэг нь өөрөө
		s[i] = 1;	// хэмжээ нь 1
	}

	cin >> q; 	// хүсэлтийн тоо
	
	while(q--) {
		int x, y;	// холбох 2 орой
		cin >> x >> y;

		int rootX = find(x);	// x оройн дээд эцгийг олно.
		int rootY = find(y); 	// y оройн дээд эцгийг олно.

		if(rootX == rootY) {	// анхны 2 оройн дээд эцэг нь ижил гэдэг нь
					// нэг компонентэд энэ 2 орой оршиж байна.
					// тиймээс юу ч хийх шаардлагагүй.
		} else {	// эсрэг тохиолдолд нэгтгэх ёстой.
			// 2 компонент нэгдэж байгаа тул нийт компонентийн тоо нэгээр хасагдана.
			comp--;
			if(s[rootX] > s[rootY]) {	// хэмжээ ихэд нь хэмжээ багатай
							// компонентийг холбоно.
				par[rootY] = rootX;	// rootY-н эцгийг rootX болгоно.
				s[rootX] += s[rootY];	// rootX эцэгтэй компонентийн хэмжээ нь нэмэгдэнэ.
				s[rootY] = 0;
			} else {
				par[rootX] = rootY;	// rootX-н эцгийг rootY болгоно.
				s[rootY] += s[rootX];	// rootY эцэгтэй компонентийн хэмжээ нь нэмэгдэнэ.
				s[rootX] = 0;
			}
		}
		cout << comp << endl;
	}

	return 0;
}