【HZNU Summer training】HDU1856 More is Better （并查集最大集合）

    此题的题意是，在一个房间里有一堆邻家♂boy，他们互相之间存在着一些py♂关系，你需要找出他们中间最大的一个朋友圈（朋友关系具有传递性），并输出这个朋友圈中的人数。

    看到朋友关系很难不想到并查集，但此题要求输出最大集合的元素个数，那么就必须做一些处理。起初我打算处理完输入后再做一遍遍历，找出每个集合的元素个数，最后找出最大值（场面过于暴力）。后来想起这道题数据规模有1e7，暴力个蛇皮自行车。遂想到在并查集处理数据的过程中把集合元素个数也顺便处理。

    先上代码：

#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int fa[10000005];
int sum[10000005];
int maxsum=1;
int find(int a) {
	return a==fa[a]?a:fa[a]=find(fa[a]);
}
void mix(int x,int y) {
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) {
		fa[fx]=fy;
		sum[fy]+=sum[fx];
		maxsum=max(maxsum,sum[fy]);
	}
}
void init(){
	for(int i=1;i<=10000000;i++){
		fa[i]=i;
		sum[i]=1;
	}
}
int main() {
	int n;
	while(cin>>n){
		maxsum=1;
		init();
		int a,b;
		for(int i=0;i<n;i++){
			cin>>a>>b;
			mix(a,b);
		}
		cout<<maxsum<<endl;
	}
	return 0;
}

   可以看到整体框架与一般的并查集裸题差不多，但多了一个sum数组，并且在mix函数中做了一些改动：

int sum[10000005];
int maxsum=1;
void mix(int x,int y) {
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) {
		fa[fx]=fy;
		sum[fy]+=sum[fx];             //元素个数处理
		maxsum=max(maxsum,sum[fy]);   //维护最大集合元素值
	}
}
void init(){
	for(int i=1;i<=10000000;i++){
		fa[i]=i;
		sum[i]=1;
	}
}

    sum数组用来存集合元素数，如何存？看下面的mix函数。

    我们知道并查集是一个树形数据结构，根节点即是find函数最终返回的节点，同时也可用它来表示整个集合。而普通的并查集中，在mix函数里，只需将两元素的根节点建立联系（即代码走不加注释的部分），这个过程相当于把一棵树的根嫁接到另一棵树的根上。现在我们知道，我们手里的这棵树（并查集）是具有一些属性的，比如元素个数，那我在嫁接的时候，顺便将这个值加到受体上，就可以完成处理，正如代码中带注释部分所示。这里需要注意的是，要找准双方的根节点，不要接反了。

    要注意的是，sum数组需要初始化为1，因为每个集合都带有它本身，元素个数是1起步的，昨天脑子抽风，memset了一套0，智力孤危。

    骚的是交题的时候，同样的代码交G++会TLE，交C++就AC，长见识了。