20131029: 并查集； 树与森林入门
今天开始学习树与森林（虽说老师早就开始讲了）， 森林就是多棵树的集合，当然，可以为空。 而树也就是在二叉树的基础上允许多分叉， 必须要掌握的是树与森林的转换，
二叉树与森林的转换， 树的性质（基本上可以由二叉树的性质类推而来）， 我们熟悉的是二叉树， 所以要多用二叉树来类比探讨树与森林的性质~
森林无疑是很有用的， 就是用起来可能比较麻烦， 其本质是集合， 集合的元素又是集合， 也就是说， 说本质为集族可能更好些， 存储方式可以选择数组或者指针链接，
但是当情况复杂时用数组可能对自己的思维有相当的挑战（当然情况简单时用数组会特别方便）。
今天首先是做了一道关于并查集的题目， 就是划分等价类的问题， 一开始我看错了， 用了很简单的思想去做，结果当然WA了， 后来明白是用并查集思想做划分， 并查集的使用包含两个基本操作， Union和Find， 分别是合并两个集合以及查看这个元素属于哪个集合， 每个集合（等价类）需要有一个代表，我们规定最远的祖先为代表。
针对并查集有两个比较有效的优化， 路径压缩与根据rank合并， 前面是为了避免退化成单链或者数据规模太大而导致搜索超时，方法是深度转化为广度， 即在查找过程中不断把
子节点挂到祖先节点上； 后者是在合并集合时将小的挂到大的上， 本质也是减少深度， 当两个集合大小相同时， 可有自己指定一种合并方式！~
最后说明一点， 并查集的实现很简单， 一个数组就够了， 但其本质是森林， 所以其实也就是森林的一种运用！~
//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!~