解决的典型问题：连通
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;
}
最低公共祖先
- 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;
}
};
