等价类

缘起

S是一个集合, 现在给出S上若干等价偶对, 需求是获取S的等价类.

分析

我们知道其实关系R是集合S*S的子集. 等价关系ER中任何两个元素之间都是等价的. 所以可以使用并查集来做. 即<a,b> 等价对，则将b 归到a下面. 为了防止数据倾斜导致树的深度分非常长. 这里将a归入b 还是b归入a要考察两者子树的元素个数. 需要将成员较少的树接入到成员较多的树. 这样通过并查集回溯修改的次数较少.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "stdafx.h"
#include <iostream>
#include <vector>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;
const int MAX_NUM = 12; // 最多12个点
typedef vector<int>::iterator it;


struct Node
{
	int root;
	int num;
} f[MAX_NUM]; // 并查集数组, 其中维护了以它为根的树的大小, 这是为了放置数据倾斜而设置的.(防止极其变态的输入)

int n; // 实际顶点的个数

void init()
{
	for (int i = 1; i<=n; i++)
	{
		f[i].num = 1;
		f[i].root = i; // 一开始每棵树只有自己
	}
}

int getf(int i){return f[i].root ==i?i:f[i].root = getf(f[i].root);} // 找爹

void merge(int i, int j) // 合并i和j
{
	int x = getf(i); // i所在树的根节点
	int y = getf(j); // j所在树的根节点
	if (x == y) return; // 如果相等的话, 不再进行下面的加法处理, 否则就多加了
	if (f[x].num<f[y].num) // 如果i所在树的节点个数小于j所在节点个数的话, 则需要将i所在树接入到j所在树中去， 这样是并查集的优化算法. 防止数据倾斜
	{
		f[x].root = y;
		f[y].num+=f[x].num; // 更新j所在树的根节点的num域
	}
	else
	{
		f[y].root = x;
		f[x].num+=f[y].num;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	init();
	int i,j;
	while(~scanf("%d%d", &i,&j))
	{
		merge(i,j);
	}
	int sum = 0; // 最后团伙的个数
	vector<int> boss[MAX_NUM]; // 老大数组
	int rboss[MAX_NUM];  // 知道老大在哪个vector中
	for (int i = 1; i<=n; i++)
	{
		if (f[i].root == i)
		{
			printf("第%d个团伙的老大是%d ",sum+1, i);
			boss[sum].push_back(i);
			rboss[i] = sum++;
			printf("该团伙有%d人\n",f[i].num); // 打印该团伙的人员个数
		}
	}
	cout << "团伙一共" << sum <<"个"<<endl;
	puts("人员构成分别是");
	for (int i = 1; i<=n;i++)
	{
		int root = getf(i);
		if (root!=i)  // 说明是小弟
		{
			boss[rboss[root]].push_back(i);
		}
	}
	for (int i = 0; i<sum;i++)
	{
		for (it x = boss[i].begin(); x!=boss[i].end(); x++)
		{
			printf("%d ", *x);
		}
		puts("");
	}
	return 0;
}
/*
测试数据
8
1 2
3 4
5 6
7 8
1 3
5 7
1 5
*/