并查集

解决的典型问题：连通
eg：首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。像畅通工程这题，问还需要修几条路，实质就是求有几个连通分支。如果是1个连通分支，说明整幅图上的点都连起来了，不用再修路了；如果是2个连通分支，则只要再修1条路，从两个分支中各选一个点，把它们连起来，那么所有的点都是连起来的了；如果是3个连通分支，则只要再修两条路。

并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点（上一级）是什么，函数find是查找，join是合并。
下面的代码可以结合http://blog.csdn.net/dellaserss/article/details/7724401的描述看，生动形象233。

int pre[1000 ];

int find(int x)//查找根节点
{ 
    if(pre[x]==x)
        return x;
    return pre[x]=find(pre[x]);
}

void join(int x,int y)  
 //判断x y是否连通，如果已经连通，就不用管了 //如果不连通，就把它们所在的连通分支合并起,

{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
        pre[fx ]=fy;
}
 

最低公共祖先

236. Lowest Common Ancestor of a Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<TreeNode*, pair<TreeNode*,int>> pre;
    void build(TreeNode* root, int level){
        if(!root)
            return;
        if(root->left) pre[root->left]=make_pair(root,level+1);
        if(root->right) pre[root->right]=make_pair(root,level+1);
        build(root->left,level+1);
        build(root->right,level+1);
        return;
        
    }
    
    
    TreeNode* find(TreeNode* root, TreeNode* high, TreeNode* low){ // include situation two levels equal
        int dif=pre[low].second-pre[high].second;
        while(dif--){
            low=pre[low].first;
        }// now the same level 
        while(low!=high){
            low=pre[low].first;
            high=pre[high].first;
        }
        return low;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(p==q) return p;
        TreeNode* res;
        pre[root]=make_pair(root,0);
        build(root,0);
        if (pre[p].first == pre[q].first) return pre[p].first;
        else if(pre[p].second < pre[q].second) res=find(root, p, q);
        else res=find(root,q,p);
        
        return res;
    }
};