UVA - 11987 - Almost Union-Find （又是並查集~）

UVA - 11987

Almost Union-Find Time Limit: 1000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu

 

Submit Status

Description

Problem A

Almost Union-Find

I hope you know the beautiful Union-Find structure. In this problem, you're to implement something similar, but not identical.

The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:

1 p q

Union the sets containing p and q. If p and q are already in the same set, ignore this command.

2 p q

Move p to the set containing q. If p and q are already in the same set, ignore this command

3 p

Return the number of elements and the sum of elements in the set containing p.

Initially, the collection contains n sets: {1}, {2}, {3}, ..., {n}.

Input

There are several test cases. Each test case begins with a line containing two integers n and m (1<=n,m<=100,000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1<=p,q<=n. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each type-3 command, output 2 integers: the number of elements and the sum of elements.

Sample Input

5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3

Output for the Sample Input

3 12
3 7
2 8

Explanation

Initially: {1}, {2}, {3}, {4}, {5}

Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}

Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3})

Collection after operation 1 3 5: {1,2}, {3,4,5}

Collection after operation 2 4 1: {1,2,4}, {3,5}

---

Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yiming Li
Note: Please make sure to test your program with the gift I/O files before submitting!

Source

Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Intermediate
Root :: Prominent Problemsetters :: Rujia Liu
Root :: Rujia Liu's Presents :: Present 3: A Data Structure Contest

 

 

 

思路：1,3比較好實現，2則有點麻煩，2屬於並查集的刪除操作，需要另設一組real[]數組來確定元素的實際地址，每刪除一個元素，就把這個元素放在最後面。。我本來以為直接把p指向q的根就行了，但發現這是錯的。如果p是葉子結點，那可以，但如果是某個集合的根呢。我們只是要把這一個元素移掉，如果直接把p指向q的根，它的葉子節點們也過去啦。。。而如果另設一組real數組的話就可以將影響降為0啦。。

 

AC代碼：

 

#include 
#include 
#include 
#define LL long long
using namespace std;

const int maxn = 200005;
int pa[maxn], real[maxn], cnt[maxn];
int n, m, vnum;
LL sum[maxn];

int find(int x) {
	return pa[x] != x ? pa[x] = find(pa[x]) : x;
}

void Union(int a, int b) {
	int a1 = find(real[a]), b1 = find(real[b]);
	pa[a1] = b1;
	sum[b1] += sum[a1];
	cnt[b1] += cnt[a1];
}

void Move(int a) {
	int t = find(real[a]);
	sum[t] -= a, cnt[t]--;
	real[a] = ++vnum;		//並查集的這裡到n了，所以要先++，之前後++的樣例沒過，檢查半天=_=||
	sum[real[a]] = a, cnt[real[a]] = 1, pa[real[a]] = real[a];
}

int main() {
	while(scanf("%d %d", &n, &m) != EOF) {
		for(int i = 0; i <= n; i++) {
			pa[i] = real[i] = sum[i] = i;
			cnt[i] = 1;
		}
		
		vnum = n;
		int ord, p, q;
		while(m--) {
			scanf("%d", &ord);
			
			if(ord == 1) {
				scanf("%d %d", &p, &q);
				if(find(real[p]) != find(real[q])) 
					Union(p, q);
			} 
			else if(ord == 2) {
				scanf("%d %d", &p, &q);
				if(find(real[p]) != find(real[q])) 
					Move(p), Union(p, q);
			} 
			else if(ord == 3) {
				scanf("%d", &p);
				int tmp = find(real[p]);
				printf("%d %lld\n", cnt[tmp], sum[tmp]);
			}
		}
	}
	return 0;
}