20131029: 并查集； 树与森林入门
天开始学习树与森林（虽说老师早就开始讲了）， 森林就是多棵树的集合，当然，可以为空。 而树也就是在二叉树的基础上允许多分叉， 必须要掌握的是树与森林的转换，二叉树与森林的转换， 树的性质（基本上可以由二叉树的性质类推而来）， 我们熟悉的是二叉树， 所以要多用二叉树来类比探讨树与森林的性质~
森林无疑是很有用的， 就是用起来可能比较麻烦， 其本质是集合， 集合的元素又是集合， 也就是说， 说本质为集族可能更好些， 存储方式可以选择数组或者指针链接，
但是当情况复杂时用数组可能对自己的思维有相当的挑战（当然情况简单时用数组会特别方便）。
今天首先是做了一道关于并查集的题目， 就是划分等价类的问题， 一开始我看错了， 用了很简单的思想去做，结果当然WA了， 后来明白是用并查集思想做划分， 并查集的使用包含两个基本操作， Union和Find， 分别是合并两个集合以及查看这个元素属于哪个集合， 每个集合（等价类）需要有一个代表，我们规定最远的祖先为代表。
针对并查集有两个比较有效的优化， 路径压缩与根据rank合并， 前面是为了避免退化成单链或者数据规模太大而导致搜索超时，方法是深度转化为广度， 即在查找过程中不断把
子节点挂到祖先节点上； 后者是在合并集合时将小的挂到大的上， 本质也是减少深度， 当两个集合大小相同时， 可有自己指定一种合并方式！~
最后说明一点， 并查集的实现很简单， 一个数组就够了， 但其本质是森林， 所以其实也就是森林的一种运用！~
[cpp] view plaincopy
//并查集的使用(森林的使用）
//关键词冲突时改变大小写不失为一种好方法
[cpp] view plaincopy
//poj： 宗教信仰
#include<iostream>
#include<cstring>
using namespace std;
int father[50001]; //初始化时每个元素为1个集合，互不相交
int Find(int x) //找到x所对应的集合，用其最古老的的祖先表示
{
if(father[x]==x) //找到祖先（这棵树对应的根节点）
return x;
father[x]=Find(father[x]); //路径压缩（将当前节点直接挂到祖先上）
return father[x]; //主要优化节点超多和退化成链时的递归搜索
}
void Union(int x, int y) //合并两个集合
{ //本来应该找到祖先再连接，但这个程序调用时传入的就是对应的祖先
father[x]=y;
}
int main()
{
int n,m,i,j;
int casenum=0;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
casenum++;
for(i=1;i<=n;++i)
father[i]=i;
int t1,t2,cnt=n;
while(m--)
{
cin>>t1>>t2;
int k1=Find(t1),k2=Find(t2);
if(k1==k2) continue; //在同一个集合中（同一颗树)
Union(k1,k2);
cnt--; //每合并一次减一次
}
cout<<"Case "<<casenum<<": "<<cnt<<endl;
}
return 0;
}
/*并查集另外一种优化的方法：rank的合并
C语言代码： 合并时将元素所在深度低的集合合并到元素所在深度深的集合。
void judge(int x ,int y)
{
fx = getfather(x);
fy = getfather(y);
if (rank[fx]>rank[fy])
father[fy] = fx;
else
{
father[fx] = fy;
if(rank[fx]==rank[fy])
++rank[fy]; //重要的是祖先的rank，所以只用修改祖先的rank就可以了，子节点的rank不用管
}
}
初始化：
memset(rank,0,sizeof(rank));
*/
//我最开始的错误做法：12 34 13 则无法通过， 而如果单纯改为减，就是n-m， 注意已经在同一集合的不需合并， 所以要采取集合划分的形式
/*
int a[50001];
while(m--)
{
cin>>t1>>t2;
if(a[t1]==0&&a[t2]==0)
cnt++;
a[t1]=a[t2]=1;
}
for(i=1;i<=n;++i)
if(a[i]==0)
cnt++;
*/
本来今天还想多刷几道的， 但后来实在是被一道题坑死了，暂时按下不表， 待我做完再说！~
Goodnight!~
补充：软件开发 , C++ ,
