[数据结构与算法]5.1 并查集

5.1 并查集

并查集是一种精巧且实用的数据结构，主要用于处理一些不相交集合的合并问题。

如果还记得紫书十一章内容的同学，这个概念肯定不是第一次见了，在讲解Kruskal算法时就已经简单介绍过这种数据结构：其中图上的结点分割成一个一个不相交的点集合，并查集将一个集合中的点用一种类似于链表(递归)的方法存储着，集合中的点不存在次序关系，只存在是否属于某个“帮派”的属性，优势就在于两个集合的合并就像链表的插入一样非常之快。当时也提到了并查集可能遇到的特殊情况：树退化成一条长链子从而降低查找速度。解决的方法是在遍历的同时，将遍历过的结点都改成树根的子节点，就可以增加下次查找的效率。

Kruskal算法：

int cmp(const int i,const int j){return w[i]<w[j];}//w表示权重
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}//返回集合编号
//但如果只为了得到集合(树)的编号(根),不需要有赋值的操作:p[x]=find(p[x])
//赋值的操作就是前面提到的对特殊情况的优化:将遍历过的点都改成树根的子节点
int Kruskal(){int ans=0; for (int i=0;i<n;i++) p[i]=i;//建立并查集 
	for (int i=0;i<m;i++) r[i]=i;//给每条边配上序号,排序后将第i小的边的序号保存在r[i]
	//排序的关键字是对象的代号,而不是对象本身,这被称为间接排序
	sort(r,r+m,cmp);//进行排序,u[i]和v[i]分别表示编号为i的结点的两个端点的序号 
	for (int i=0;i<m;i++){int x=find(u[r[i]]),y=find(v[r[i]]);
		if (x!=y) {ans+=w[r[i]]; p[x]=y;}//ans+=w[r[i]]相当于加上边的权重,这个很好理解
		//p[x]=y相当于将v结点所在树接到u结点的根上(因为不考虑树的形态,只要保证连通即可) 
	} return ans; 
} 

这里我们接着黑书的内容从基本的操作更加细致的了解并查集。

并查集操作的简单实现

首先我们先设定一个简单的背景：在一个城市中有n个人，他们组成不同的“帮派”，给出一些人之间的关系，例如：1号，2号是朋友，1号，3号是朋友，那么他们都属于一个帮派。现在的问题是，在这些关系下，有多少帮派，没人属于哪个帮派。

分析：简单来说，n个结点的图，给定m条有向边，问你有多少个连通分量，每个结点属于哪个分量。

这里就用并查集，将n个结点划分为不相交的集合，然后用一个集合中的某个结点来代表所在集合。

并查集的初始化

定义数组s[i]是以节点i为元素的并查集，在开始还没有处理朋友与朋友之间的关系时，每个人都属于一个独立的集，并且以元素i的值表示它的集合s[i]。

并查集的合并

例如加入第一个朋友关系(1,2)，就是将朋友1所在的“帮派”与朋友2所在的“帮派”进行合并。递归查找到结点1所在的集为1，结点2所在的集为2，将结点1的集1改成集2(改哪个没什么实际影响)。

加入第二个朋友关系(1,3)，递归查找到结点1所在的集为2，结点2的集为2，结点3所在的集为3，将元素2的集2合并到集3，此时结点1，2，3属于一个集。

这里的合并并不是一个很好的合并，因为大家可以发现一个集合只有3个元素，但是链的长度已经达到了3，树退化成了长链，查找的复杂度会很高。

并查集的查找

在前面的操作中就已经需要查找操作了：查找元素的集是一个递归的过程，例如我们查找上面的并查集中结点1的所在集。

此时s[1]不等于1，说明1不是结点1的所在集，对s[1]=2进行查找，s[s[1]]=s[2]=3，此时s[2]不等于2，继续向下查找，s[3]=3，说明3是1的所在集。

可以发现像上面这种退化成长链的情况会影响查找的速度，所以在实际操作的过程中还需要很多的优化

统计有多少个集

如果s[i]=i，说明这是一个根结点，根结点的数量即是集的数量。

看一下并查集在实际问题中的运用。

hdu 1213 “How Many Tables”

有n个人一起吃饭，有些人互相认识，认识的人想坐一桌，例如A认识B，B认识C，那么A,B,C就会坐同一桌。

问需要给出多少张桌子。

分析：就是我们拿来做例子的帮派问题。

#include<iostream>
using namespace std;
int s[1050];
void init_set(int n){for (int i=1;i<=n;i++) s[i]=i;}//初始化并查集
int find_set(int x){return x==s[x]?x:find_set(s[x]);}//查找并查集,s[x]=x时,说明为集合的根节点
void union_set(int x,int y){x=find_set(x); y=find_set(y);//合并并查集,找到两个集的编号 
	if (x!=y) s[x]=s[y];//如果不是同一个集,将其中一个集代表元素的s值改成另一个集合的代表元素即可 
}
int main(){int t,n,m,x,y; cin>>t;
	while (t--){cin>>n>>m; init_set(n);//初始化并查集 
		for (int i=1;i<=m;i++){cin>>x>>y; union_set(x,y);}//合并两个朋友的所在"帮派" 
		int ans=0; for (int i=1;i<=n;i++) if (s[i]==i) ans++;//统计集的个数
		cout<<ans<<endl; 
	} return 0;
} 

并查集操作的优化

以上都是最简单的操作，在实际的使用中往往性能比较差，下面介绍一些优化的方法。

合并的优化

给集合对应的树添加高度的属性，将高度较小的树加入到高度较大的树的根节点下。

int height[maxn];//表示集i对应树的高度
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
} 

查询的优化

这个优化我们在Kruskal算法中就见到过了，就是在查询搜索的过程中，将路径上的结点的前一个结点全部改成根节点。

这种优化方式降低了树的深度，提高了下次查询的效率。

代码的话比较简单，加一个赋值即可：

//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);}

整体的模板如下：

int height[maxn];//表示集i对应树的高度
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}

习题

poj 2524 “Ubiquitous Religious”

直接看分析

分析：没有看题，看了一下数据感觉就是前面说的问题，改了一下直接过了，没啥好说的。

#include<iostream>
using namespace std; 
int height[50010],s[50010];//表示集i对应树的高度
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}
int main(){int n,m,x,num=0,y;
	while (cin>>n>>m&&n!=0&&m!=0){num++; init_set(n);//初始化并查集 
		for (int i=0;i<m;i++){cin>>x>>y; union_set(x,y);}//将x和y所在的集合并 
		int ans=0; for (int i=1;i<=n;i++) if (s[i]==i) ans++; printf("Case %d: %d\n",num,ans);//统计集的个数并打印
	}return 0;
}

poj 1611 “The Suspects”

分析：也是一个简单的并查集问题，不过需要添加一个属性人数来表示每个集团的人数(我开始的时候以为用没有优化过的合并，然后用树的高度表示人数结果WA了)，在合并两个集合时，将人数进行相加。最后查找合并后0号学生所在集团的人数。

#include<iostream>
using namespace std; 
int sum[50010],s[50010];//这里sum表示集团中的人数 
void init_set(int n){//初始化并查集,这里人数初始化为1 
	for (int i=0;i<n;i++) {s[i]=i; sum[i]=1;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:x=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (x!=y){s[y]=x; sum[x]+=sum[y];}//两个集团的人数进行合并相加 
}
int main(){int n,m,x1,x,k;
	while (cin>>n>>m&&n!=0){init_set(n);//初始化并查集 
		for (int i=0;i<m;i++){cin>>k>>x1; 
			for (int j=1;j<k;j++){cin>>x; union_set(x,x1);} 	
		}cout<<sum[find_set(0)]<<endl;
	}return 0;
}

poj 1703 “Find them，Catch them”

n个人划分成两个集团，现在给你m条信息，一条信息包括符号ch和编号x，y。如果符号ch为D表示编号为x和y的两人不在同一组，符号为A需要你在已有的信息下输出编号为x和y的两人，在同一组，不在同一组，或你不确定。

分析：第一想法是将n个人都划分到一个集团进行模拟，但这么做有一个问题就是并查集只有合并没有差集的操作。这时就想到一个解法，对1-n的人做一个映射n+1~2n，规定某个集团的结点有i表示有这个人，某个集团的结点中有i+n表示一定没有这个人，其他的都不是确定状态。

如果两个人在一个集团，那么只需要对于某个集团他们同时属于或者同时不属于(因为总共只有两个集团)，同理如果两个人不在一个集团，那么只需要对于某个集团他们其中的一个人属于另一个人不属于即可。

#include<cstdio>
using namespace std; 
int height[200010],s[200010];//表示集i对应树的高度
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);}
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}
int main(){int t,n,m,x,y; char ch[2]; scanf("%d",&t);
	for (int i=0;i<t;i++){int n,m; scanf("%d%d",&n,&m); init_set(2*n);//初始化并查集
	//这里对1~n的人建立一个映射到n+1~2n,其中一个集团拥有结点i(i在1~n之间)表示集团中有这个人
	//一个集团中拥有结点i+n(i在1~n之间)表示这个集团中没有结点i这个人 
		for (int j=0;j<m;j++){scanf("%s%d%d",&ch,&x,&y); 
			if (ch[0]=='D'){union_set(x+n,y); union_set(x,y+n);}//x所在的集团中没有y,y所在的集团中没有x 
			else{int a=find_set(x),b=find_set(y),c=find_set(x+n),d=find_set(y+n); 
				//对于某一个集团同时确定拥有x和y或者确定同时不拥有x和y,都能说明x和y是一个集团
				if (a==b||c==d) printf("In the same gang.\n");
				//同理,如果某一个集团同时确定不拥有x但拥有y或确定拥有x但不拥有y,也能说明x和y不是一个集团 
				else if (a==d||b==c) printf("In different gangs.\n");
				else printf("Not sure yet.\n");	
			}  
		}
	}return 0;
}

开始的时候时间超限了，我以为是爆栈了，换了一个不爆栈的写法结果发现还是没过，最后对比别人的代码发现用scanf和printf就能过hhh。

poj 2236 “Wireless Network”

给定一个计算机网络中n台电脑的位置和距离D，n台电脑初始状态都是坏的。接下来再给若干条指令，(O，i)表示修复电脑i，(S，x，y)表示寻味电脑x和y是否能够联通，如果两台修复好的电脑之间的距离小于D说明可以连通，且连通具有传递性。

分析：和一般的问题不同，只有修复好的电脑才能参与初始化，每修复好一台电脑即与之前修复好的，且之间距离小于D的电脑所在的集团进行合并。

比起前一题反而难度要低了一些：

#include<cstdio>
using namespace std;
int x[1010],y[1010],s[1010],height[1010],repair[1010];//height表示集i对应树的高度,repair存储修复好的电脑 
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}//两点之间距离的平方(不开根号的原因是因为sqrt有一定的复杂度) 
double dis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);} 
int main(){int n,d,num=0; char ch[2]; scanf("%d%d",&n,&d); for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); d=d*d; 
	while (scanf("%s",ch)){int p,q;
		if (ch[0]=='O'){scanf("%d",&p); repair[num++]=p;//将修复好的电脑加入repair数组 
			//题目给的数据中会出现重复修复的情况所以需要排除这种情况 
			for (int i=0;i<num-1;i++) if (repair[i]!=p&&dis(repair[i],p)<=double(d)) union_set(repair[i],p);			
		}//同属于同一集团的电脑可以连通 
		else {scanf("%d%d",&p,&q); if (find_set(p)==find_set(q)) printf("SUCCESS\n"); else printf("FAIL\n");	
		}
	}return 0; 
}

poj 2492 “A Bug’s Life”

给定n只雌雄分明的虫子和m条信息，每条信息告诉你哪两只虫子谈恋爱了，需要你判断是否存在同性恋的虫子。

分析：······很恶趣味的一道题的感觉，将雌雄的性别看作两个集团，先出的信息告诉你哪两个虫子一定不在一个集团，我们用前面题同样的方法建立一个映射进行处理。

每次出现有新的信息，我们就判断新的信息出现的两个虫子是否同时属于或者同时不属于一个集团，如果有则出现同性恋的情况。

代码就不写了和poj1703的思路是完全一样的。

poj 1988 “Cube Stacking”

n个箱子，初始时每个箱子单独为一列，给定m条信息：对于M,x,y，表示将x箱子所在的一列箱子搬到y所在的一列箱子上，对于C,x，表示求箱子x下面有多少个箱子。

分析：对于箱子而言，s表示箱子所在列最下面的箱子编号，依旧是一个并查集的问题。但是由于M指令表示将x箱子所在的一列箱子搬到y所在的一列箱子上，那么union_set指令不可以使用优化过的版本(因为优化过的版本，是将数量少的合并到数量多的里面)。

另外，还需要一个属性sum表示某个集团(列)的箱子个数，一个属性dis表示某个箱子当前下面还有多少个箱子。合并时需要对两个属性进行调整(箱子个数相加，某个箱子当前下面的箱子个数加上被合并列的箱子总数)。

于是有下面的代码：

#include<cstdio>
using namespace std;
int s[30010],num[30010],dis[30010];//num表示箱子i对应列中箱子的个数,dis表示箱子i到最下面箱子中间的箱子数 
void init_set(){//初始化并查集,每列的箱子个数初始化为1,dis设置为0 
	for (int i=1;i<=30010;i++) {s[i]=i; num[i]=1; dis[i]=0;}
}//并查集查询 
int find_set(int x){return x==s[x]?x:find_set(s[x]);}
//将x箱子所在的一列箱子搬到y所在的一列箱子上,此时x下面的箱子需要加上y整列的箱子个数  
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	s[x]=y; dis[x]+=num[y]; num[y]+=num[x]; 
}
int main(){int n,x,y; char ch[2]; scanf("%d",&n); init_set();
	for (int i=0;i<n;i++){scanf("%s",ch);
		if (ch[0]=='M') {scanf("%d%d",&x,&y); union_set(x,y);}
		else {scanf("%d",&x); find_set(x); printf("%d\n",dis[x]);}
	} return 0;
}

因为这里压缩路径比较难写，所以我本来想按照没有优化过的版本来写，结果发现会超时，所以还是需要压缩路径的优化。

但是这里的压缩路径存在一个问题：dis值是一个单对于箱子的概念，即使对于同一集团的箱子，他们的dis值很显然是不同的，所以将它们从一条链的结构转化为一个二层的树时，需要将下层节点(从一列的箱子角度来看就是上层的箱子)的dis值加上上层节点的dis值。

#include<cstdio>
using namespace std;
int s[30010],num[30010],dis[30010];//num表示箱子i对应列中箱子的个数,dis表示箱子i到最下面箱子中间的箱子数 
void init_set(){//初始化并查集,每列的箱子个数初始化为1,dis设置为0 
	for (int i=1;i<=30010;i++) {s[i]=i; num[i]=1; dis[i]=0;}
}//并查集查询 
int find_set(int x){if (s[x]==x) return x; int tmp=s[x];
	s[x]=find_set(s[x]); dis[x]+=dis[tmp]; return s[x];
}
//将x箱子所在的一列箱子搬到y所在的一列箱子上,此时x下面的箱子需要加上y整列的箱子个数  
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	s[x]=y; dis[x]+=num[y]; num[y]+=num[x]; 
}
int main(){int n,x,y; char ch[2]; scanf("%d",&n); init_set();
	for (int i=0;i<n;i++){scanf("%s",ch);
		if (ch[0]=='M') {scanf("%d%d",&x,&y); union_set(x,y);}
		else {scanf("%d",&x); find_set(x); printf("%d\n",dis[x]);}
	}
}

依照代码来说合并是对集合根节点的dis值进行修改，而查询相当于将合并后的新树转化成一个二层树，并且对其中的dis值进行一个调整和修改(需要调整的原因是箱子摆放的结构实际是线性结构而不是树状结构)，然后得到我们所要的结果(这也是为什么在输出之前需要进行查询的原因)。

这个问题困扰了我很久，很无奈我到现在会写但也理解的并不是完全明白。

这里的箱子总数不是n，初始化的时候需要注意一下。

poj 1182 “食物链”

题面比较长，就不打出来了

分析：这个问题和前面poj1703两个帮派的问题也是非常类似的，但是poj1703中每个人属于两个帮派中的一个，这个问题中每个人都属于三个帮派中的一个，所以在映射的方便也需要进行一个简单的调整。

节点i映射节点n+i和节点2n+i，某个集团中编号为i的节点可以吃编号为n+j的节点，被编号为2n+k的节点吃。同理：编号为n+i的节点可以吃编号为2n+j的节点，被编号为k的节点吃；编号为2n+i的节点可以吃编号为j的节点，被编号为n+k的节点吃。三种关系保持一个环状结构。(1<=i,j,k<=n)

#include<cstdio>
int s[150010],height[150010];//height表示集i对应树的高度
void init_set(int n){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=n;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}
int main(){int n,k,m,x,y,num=0; scanf("%d%d",&n,&k); init_set(3*n);
	for (int i=0;i<k;i++){scanf("%d%d%d",&m,&x,&y);
		if (x<1||x>n||y<1||y>n) {num++; continue;}//第一种情况,数据违规
		if (m==2&&x==y) {num++; continue;}//第三种情况,X吃X 
		if (m==1){//x和y同类,如果x能吃y或者y能吃x,说明是假话 
			if (find_set(x)==find_set(y+n)||find_set(y)==find_set(x+n)) num++;
			else{//否则是真话,x和y是同类,将x和y连通映射进行合并 
				union_set(x,y); union_set(x+n,y+n); union_set(x+2*n,y+2*n); 
			}
		} 
		else{//x吃y,如果y能吃x或者x和y同类说明是假话 
			if (find_set(x)==find_set(y)||find_set(y)==find_set(x+n)) num++; 
			else{//否则是真话,将x能吃y的关系连同映射进行合并 
				union_set(x,y+n); union_set(x+n,y+2*n); union_set(x+2*n,y); 
			}
		} 		
	}printf("%d",num); return 0;
} 

需要的是二选一的结构到环状结构的转换，理解了还是很简单的。

hdu 3635 “Dragon Balls”

给定n个龙珠(嗯，就是那个龙珠)，和q条指令，T x y：表示将x所在城市的龙珠都移动到y所在的城市，Q x：表示询问编号为x的龙珠现在在哪个城市，这个城市有几个球，还有这个龙珠移动过几次。每颗龙珠开始都在他们编号对应的城市。

分析：很明显的并查集问题了，一个城市代表一个集团，但是这里需要你求龙珠移动的次数，所以需要另外建立一个属性。

总体来说是和poj1988移箱子那题是非常类似的一道题：

#include<cstdio>
using namespace std;
int s[10010],num[10010],move[10010];//num表示城市中的龙珠个数,move表示某个龙珠的移动次数 
void init_set(int n){//初始化并查集,每个城市的龙珠个数初始化为1,移动步数设置为0 
	for (int i=1;i<=n;i++) {s[i]=i; num[i]=1; move[i]=0;}
}//并查集查询,压缩路径需要进行的调整和移动箱子那个问题一样 
int find_set(int x){if (s[x]==x) return x; int tmp=s[x];
	s[x]=find_set(s[x]); move[x]+=move[tmp]; return s[x];
}
//并查集合并,不用对x所在列所有的元素进行的move数进行++  
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (x!=y) {s[x]=y; num[y]+=num[x]; move[x]++;} 
}
int main(){int n,m,T,x,y; char ch[2]; scanf("%d",&T); 
	for (int i=0;i<T;i++){scanf("%d%d",&n,&m); init_set(n); printf("Case %d:\n",i+1);
		for (int j=0;j<m;j++){scanf("%s",ch);
			if (ch[0]=='T') {scanf("%d%d",&x,&y); union_set(x,y);}
			else {scanf("%d",&x); int x1=find_set(x); printf("%d %d %d\n",x1,num[x1],move[x]);}
		}
	}return 0; 
}

反正我就是就会写，但不能完全理解这个模板。

hdu 1856 “More is better”

一共有10000000个男生，其中某些男生之间存在“朋友关系”，并且朋友的朋友也是朋友。现在需要你去寻找男生帮忙(寻找来的男生当然是越多越好)，但是你寻来的男生之间必须是直接的或者间接的朋友关系，问你最多能寻找来多少个男生。

分析：·······以为很难其实非常简单的问题，就是男生之间构成了若干个集，求最大集的元素个数即可。

这个代码太水了·····就不写了。

hdu 1272 “小希的迷宫”

题面请点击这里

分析：就是给定若干条边，需要你判断若干条边构成的图的所有结点是否全部连通，是否成环。

首先判断是否成环，即判断新添加进去的边的两个结点是否属于同一个集团(属于同一棵树的两个结点连边会构成环)。

所有边上的点合并完成之后，还需要判断整个图的任意两个点是否连通。事实上，如果为连通图，点的个数=边的个数+1，用一个num记录边的个数，用一个集合记录点的个数即可。

我这个代码应该是网上的版本中比较好理解的一个了。

#include<cstdio>
#include<set>
using namespace std;
int s[100001],height[100001];//height表示集i对应树的高度
void init_set(){//初始化并查集,树的高度初始化为0 
	for (int i=1;i<=100001;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}
set<int>room;//room表示图中点的集合 
int main(){int x,y,num,flag; num=0; room.clear(); init_set(); flag=1;//num表示边的数量,flag表示是否存在环 
	while (scanf("%d%d",&x,&y)&&x>=0&&y>=0){
		if (x==0&&y==0){//出现0 0时,对之前构成的图进行分析判断 
			if (flag==0) printf("No\n");//如果存在环,说明对某两个点有两条路径
			//如果不存在环,需要判断这个图中的点是否全部连通,即点的个数=边的的数量+1 
			else if (room.size()==num+1||(room.size()==0&&num==0)) printf("Yes\n"); 
			else printf("No\n");
			flag=1; init_set(); room.clear(); num=0;//重新初始化所有的条件 
		}//如果某条边的两个点属于同个集(即同一棵树),同一棵树的两个点连边会构成环 
		else if (find_set(x)==find_set(y)) flag=0;
		else {union_set(x,y); num++; room.insert(x); room.insert(y);}//两个点所在集合并,集合添加新点 
	} return 0;
}
 
 

hdu 1325 “Is It A Tree”

和前一题是几乎完全相同的一题，不多作赘述。

hdu 1198 “Farm Irrigation”

题面请点击这里

分析：就是问构成的农场长方形版图，最少需要多少个灌溉点(水源)。相邻的版块如果水流可以相接，那么可以共用一个水源。

那么这个问题就很简单了，一块一块的遍历每个板块，每个板块开始的时候都是用的独立的水源，然后和该板块周围(左边和上面)的板块进行比较，判断有没有相交(这里的相交不是集的相交而是水流的相交)，如果相交就将新板块并入周围的集，共用一个水源即可。

预先对11个板块进行二进制编码的处理：

上方向对应二进制的第1一位，右方向对应第二位，下方向对应第三位，左方向对应第四位。例如A板块对应的二进制编码即是1001=9，B对应1100=12·······

对输入的ABC·····进行编码的转化可以得到对应的编码，编码反过来可以得到某个方向的出水情况。例如A板块对应的编码9，(9/8)&1=1表示上方有水流，(9/4)&1=0表示右边没水流，(9/2)&1=0表示下方没水流，(9/1)&1=1表示左边有水流。

(编码/2的某次方)&1表示某个方向是否有水流。

判断新遍历的板块能否并入周围的集，即判断当前板块左边是否有水流和当前板块左边板块的右边是否有水流(听着有点绕)，同理还需要判断当前板块上边是否有水流和当前板块上边板块的下边是否有水流。

代码如下：

#include<cstdio>
using namespace std;
int s[2501],height[2501];//height表示集i对应树的高度
char ch[50][50]; 
void init_set(){//初始化并查集,树的高度初始化为0 
	for (int i=0;i<=2500;i++) {s[i]=i; height[i]=0;}
}//并查集查询 
int find_set(int x){return s[x]==x?x:s[x]=find_set(s[x]);} 
//并查集合并 
void union_set(int x,int y){x=find_set(x); y=find_set(y);
	if (height[x]==height[y]){height[x]=height[x]+1; s[y]=x;}//两个树一样高,无法用一个树覆盖另一个树,合并后树的高度+1
	else if (height[x]<height[y]) s[x]=y;//y的树比较高,用y的树来覆盖x树,高度保持为y树的高度 
	else s[y]=x;//x的树比较高,用x树来覆盖y树,高度保持为x树的高度 
}//板块的二进制编码转化 
int change(char ch){
    switch(ch){
        case 'A':return 9; case 'B':return 12; case 'C':return 3; case 'D':return 6;
        case 'E':return 10; case 'F':return 5; case 'G':return 13; case 'H':return 11;
        case 'I':return 7; case 'J':return 14; case 'K':return 15;
    }
}
int main(){int x,y;
	while (scanf("%d%d",&x,&y)&&x>=0&&y>=0){init_set(); getchar();//字符的单个输入输出最好还是用getchar 
		for (int i=0;i<x;i++){for (int j=0;j<y;j++){
				ch[i][j]=getchar();//由于并查集是一维数组,需要将二维数组通过编码的方式转化为一维数组 
				//当前遍历的格子的上方与当前遍历格子上方格子的下方进行匹配,如果都有水流就进行合并 
				if (i>0&&((change(ch[i][j])>>3)&1&(change(ch[i-1][j])>>1))) union_set(i*y+j,(i-1)*y+j);
				//当前遍历的格子的左方与当前遍历格子左方格子的右方进行匹配,如果都有水流就进行合并
				if (j>0&&(change(ch[i][j])&1&(change(ch[i][j-1])>>2))) union_set(i*y+j,i*y+j-1);
			}getchar();//记得换行 
		}int ans=0;//统计集团个数 
		for (int i=0;i<x;i++) for (int j=0;j<y;j++)	if (s[i*y+j]==i*y+j) ans++;	
		printf("%d\n",ans);
	} return 0; 
}

hdu 2586 “How far away”

就是最近公共祖先问题，这里不作介绍，留到后面的图论部分进行处理(因为现在即使用并查集+深搜搞定了，也不是这类问题最常用的模板解法)。

hdu 6109 “数据分割”

题面请点击这里

分析：看了一下题解，基本上都是用set来维护的，虽然说是百度之星的初赛题，但是题目的设定并不严格，没有说明最后剩余的几个约束条件是否能够满足题目的要求。

我也不太明白启发式合并的概念，只能过一段时间再见了。