树和二叉树——并查集
第1关：并查集(数组)
任务描述
本关任务：学习并查集的原理，并利用并查集编程求解兴趣社团划分的问题。
小葵班级里有n个学生，好朋友之间会有共同兴趣爱好，若小朋友x和小朋友y有共同兴趣爱好，小朋友y和小朋友z也有共同兴趣爱好，则小朋友x、y和z能组成一个兴趣社团，现在给出m对小朋友存在共同兴趣爱好，请计算出小葵班里n个小朋友最少可以组成多少个兴趣社团（0<=x,y,z<n）。
相关知识
为了完成本关任务，你需要掌握：1.并查集，2.求解思路。
并查集
并查集是一种树形的基础数据结构，在很多地方都有应用，能够快速高效的处理一些不相交集合的合并与查询操作，有点类似数据结构中森林的概念。
并查集的主要操作如下：
- 初始化：程序开始时将所有结点x所在的集合设置为其自身，用数组F表示为：F[x]=x。
- 查找：查找元素x所在的集合，即其根结点F[x]，初始时每个元素的根结点都是自身x，在经过若干个合并操作后，某个元素的根结点将可能被修改为另外某个结点的根结点，因此此时的根结点查询需要使用递归的思想进行查询：
function(x)
{
return (x==F[x])? x:function(F[x]);
}- 合并：将两个元素a和b所在的集合F[a]和F[b]合并为一个集合，合并规则如下
// 如果两个元素的根结点不一样，则他们不属于同一个集合，则合并根结点，让其中一个根结点指向另外一个
if function(a) != function(b):
F[function(b)] = function(a)求解思路
本关任务是求解最少可以组成多少个兴趣社团，那么借助题目里描述的规则，把有相同兴趣爱好的小朋友都组合在一个兴趣社团里，这样形成的社团集合数量是最少的。
基于以上分析，运用并查集能够非常方便的操作小朋友所在兴趣社团的组合。初始时，让所有的小朋友各自为一个兴趣社团，总量为n，然后根据小朋友间的共同兴趣爱好记录，将小朋友合并在一个兴趣社团，那么总的兴趣社团数量减1，处理完所有记录之后，余下的社团数量就是最少的兴趣社团总数。
编程要求
本关的编程任务是补全右侧代码片段find、merge和main中Begin至End中间的代码，具体要求如下：
- 在
find中，查找元素x在数组F中所在的集合，即根结点的值，并返回该值，初始时每个元素在自己所属的集合（F[x]=x）。 - 在
merge中，尝试合并两个元素a和b，若他们所属不同集合，则合并它们，并返回true，否则返回false。 - 在
main中，按下面案例中的输入格式读取相应数据，并调用以上函数完成所有元素的合并，并输出合并后的集合的数量，即兴趣社团的最少数量。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
10 4
1 2
3 4
7 3
7 4
预期输出：
7
输入格式：
第1行：n m，表示有n个小朋友，有m对小朋友之间存在共同兴趣爱好
第2~m+1行：每行两个整数x和y，表示小朋友x和y有共同兴趣爱好，0<=x,y<n
输出格式： 最少兴趣社团个数
#include <iostream>
#include <cstdio>
const int maxn = 50005;
int F[maxn];
int find(int x)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
return (x == F[x])? x:find(F[x]);
/********* End *********/
}
bool merge(int a,int b)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
if(find(a) != find(b))
{
F[find(a)] = find(b);
return true;
}
else{
return false;
}
/********* End *********/
}
int main(int argc, const char * argv[]) {
for (int i=0; i<maxn; i++)
{
F[i] = i;
}
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int n,m,i,a,b;
scanf("%d%d",&n,&m);
for(i = 0; i < m; i++)
{
scanf("%d%d",&a,&b);
if(merge(a,b))
n--;
}
printf("%d\n",n);
/********* End *********/
return 0;
}第2关：亲戚关系
任务描述
本关任务：对于亲戚关系问题，现给出一些亲戚关系的信息，如Marry和Tom是亲戚、Tom和Ben是亲戚等，需要从这些信息中推出Marry和Ben是否为亲戚。 输入： 第一部分以N、M开始。N为问题涉及的人的个数（1≤N≤20000）。这些人的编号为1、2、3、...、N。下面有M行（1≤N≤1000000），每行有两个数ai、bi，表示已知ai和bi是亲戚。 第二部分以Q开始。以下Q行对应Q个询问（1≤Q≤1000000），每行为ci、di，表示询问ci和di是否为亲戚。 输出： 对于每个询问ci、di，输出一行，若ci和di为亲戚，则输出“Yes”，否则输出“No”。
问题分析
亲戚关系是一种典型的等价关系。将每个人抽象称为一个点（每个点用其编号唯一标识），输入数据给出M个边的关系，当两个人是亲戚的时候两点间有一条边，很自然地就得到了一个N个顶点、M条边的图论模型，在图的一个连通块中的任意点之间都是亲戚。对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通块中。
测试输入：
10 7 //N=10,M=7
2 4 //表示2和4是亲戚
5 7 //表示5和7是亲戚
1 3 //表示1和3是亲戚
8 9 //表示8和9是亲戚
1 2 //表示1和2是亲戚
5 6 //表示5和6是亲戚
2 3 //表示2和3是亲戚
3 //Q=3
3 4 //问3和4是否为亲戚
7 10 //问7和10是否为亲戚
8 9 //问8和9是否为亲戚
预期输出：
Yes
No
Yes
#include <stdio.h>
#define MaxSize 20000
typedef struct node
{
int data; //结点对应人的编号
int rank; //结点对应秩
int parent; //结点对应双亲下标
} UFSTree;
void MAKE_SET(UFSTree t[],int n) //初始化并查集树
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int i;
for(i = 1; i <= n; i++)
{
t[i].rank = 0;
t[i].parent = i;
}
/********* End *********/
}
int FIND_SET(UFSTree t[],int x) //在x所在子树中查找集合编号
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
if(x != t[x].parent)
t[x].parent = FIND_SET(t,t[x].parent);
return t[x].parent;
/********* End *********/
}
void UNION(UFSTree t[],int x,int y) //将x和y所在的子树合并
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int rx = FIND_SET(t,x);
int ry = FIND_SET(t,y);
if(rx != ry)
{
if(t[x].rank < t[y].rank)
{
t[x].parent = ry;
}
else{
t[y].parent = rx;
if(t[x].rank == t[y].rank)
t[x].rank++;
}
}
/********* End *********/
}
int main()
{
int i,m,n;
UFSTree t[MaxSize];
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int a,b,q;
scanf("%d%d",&n,&m);
MAKE_SET(t,n);
for(i = 0; i < m; i++)
{
scanf("%d%d",&a,&b);
UNION(t,a,b);
}
scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d%d",&a,&b);
a =FIND_SET(t,a);
b =FIND_SET(t,b);
if(a == b)
printf("Yes\n");
else
printf("No\n");
}
/********* End *********/
}