所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
- 并查集是什么
图的信息就是点集合 + 边集合。
并查集在一开始就是表示点集合，但是这些点是一群孤立的点，之后就是通过union操作+边集合信息，把点连接起来，在这种连接的过程中， 可以使用find操作来知道当前的两个点之间是否是连通的。
- 并查集的具体实现
并查集使用一个hashmap来装所有结点，以及该结点对应的总领导（key是结点，value是结点对应的总领导）。这张表叫parent、father表或者boss表。
一开始全是孤立点的时候，每个结点的总领导就是自己。根据边进行点连接的时候，就相当于两家公司进行合并，此时任意选其中一个公司的总领导作为合并后的总领导。 具体过程就是：先使用find操作找到两个结点的总领导ceo1，ceo2，然后把一个总领导（例如ceo1）的总领导变为ceo2。如果find(A) == find(B)，那么说明A和B在本来就是同一家公司工作。
find操作，可以找到一个结点的总领导（CEO）结点，而并不关心中间领导，由于信息是实时更新的，因此parent[x]并一定就是x的总领导，而是要检查parent[x]是不是还存在领导。 而如果parent[x] == x的时候，也就是ceo的领导是自己的时候，那就是遇到终止条件。 所以常规解法是一步步向上去找,消耗时间O(N)，代码如下： int find(int x) { if (parent[x] == x) { return x; } return find(parent[x]); }
但是，实际上，在找总领导的过程中，可以实时更新所有查询路径上的点的总领导。这样，find操作时间从O(N)优化到接近O(1)。 优化代码如下： compressed_find(){ if (parent[x] == x) { return x; } return parent[x] = compressed_find(parent[x]); }
union操作就是两家公司合并的操作。操作过程就是，先find到两家公司的CEO，然后把其中一个指向另一个，代码如下: void union(int a, int b) { int root_a = find(a); int root_b = find(b); if (root_a != root_b) { // 如果不属于同一公司 parent[root_a] = root_b; } }
union操作时间也是O(1)。
所以，并查集的模板就是：
class UnionFind {
int find(int x);
void union(int a, int b);
vector
- 并查集使用情况
关于点的合并或者点的连边，关于集合的合并，查询，一般用并查集。但注意并查集不提供删边操作。
- 并查集其他技巧：
（1）求连通区域的个数。并查集可以加一个变量来表示公司的个数（连通区域的个数）。初始时候该变量为元素个数，每次union操作时候，只要两个点不属于一个公司时候，将变量减1。
也可以在建立连通图后计算：通过遍历每一个节点x，看其parent[x]是否等于自己，如果相等，算作一个区域数。 同理，想要知道每片连通区域的具体结点信息，可以遍历parent数组，将区域的parent结点作为key，将子节点存入指向的vector。
（2）知道某些点之间互相连通的时候，可以O(n)时间建立连通，原理就是把其他所有点连接到第一个点上，那么自然所有点就连通了。
（3）并查集可以加一个size数组来记录以key为总领导的公司的员工数量。size数组只有在该key确实是CEO时候去查才有意义，否则没意义。
具体题目
261. Graph Valid Tree
题意：验证图是不是树，给出的是结点以及结点直接连接的信息。给出的图信息是点，加边信息。
解：树的概念：树是连通且不存在回路（环）的图，也意味树有一个性质，就是边的数量等于顶点数量减1。
所以验证图是不是树要满足两个条件，一个是图上的任意两点之间连通，第二是图不存在环。判断无向图是否有环，只需要建立标记数组，只要访问回原来结点，那么就有环。
还有一个可以不检测有环的方法：只需要判断边的数量是不是顶点数量减1就可以。这样只需满足这一条件，再加上图是连通的，就满足图是树了。
方法一：dfs。首先再次说一下，dfs本质就是树结构的回溯，对于图，也就是选择一个作root。 对于无向图，存在环的判断就是：遍历时候一旦遇到已经经过dfs处理访问过的结点，那么就存在环。但是其中有一个特例，因为两个结点互为邻居，所以加入邻居结点的时候，由于父节点一定是已经访问过，所以常规dfs情况下，只需要去掉访问过的结点就行了，但是判断环的dfs中我们不能知道一个vistited结点是因为有环所以造成找到visited结点还是因为天生的找到父节点的情况，所以我们改变进入下一层的条件：明确的指出，排除掉邻居是父节点的情况。
方法二：bfs。分为三种状态，正在访问状态，未访问状态，和访问结束状态。bfs的时候，如果邻居结点都被压栈，那么状态为已访问。结点进入队列后标记为正在访问状态。结点处理邻居结点的时候，如果邻居结点处于正在访问状态，那么返回false；如果是已访问状态，那么不用压栈。
方法三：并查集。对于一个pair，看两个连接的点在已构建出的图中是否属于同一个公司，如果属于同一个公司，那么说明他们除了相互连接外，还有其他路径连通，所以就是存在环。
另外：判断是否连通，就看边的数量是不是顶点减1，如果是，那么说明是连通的。
此题还可以把方法一、二进行优化，比如一开始就看边和点的关系是不是满足tree，不满足直接返回false，如果满足，那么不可能存在环，问题就简化为判断图是否是连通的。
721. Accounts Merge
题意：找到所有人和其对应的邮箱的列表，人名不是id，邮箱才是id。
解：此题是图的问题，如果不转化为图（也就是不转化为合适的数据结构），而只是扫描的话，就会发现很难将当前处理的结果存入之前的结果。
所以还是利用合适的数据结构来解题会比较舒适。首先，将email作为id建立关系图，处于同一账户元素里面的email是互相连通的，但是谁作为第一邻居，其实是无所谓的，简单起见，把第一个email和剩余email相连，这样所有email之间都连通了。这样扫描一遍所有账户后，就得到了email的邻接表表示的图。
另外，第一遍扫描所有账户的时候，新建hash表，建立email指向用户名的映射，这样方便找到email对应的用户名。另外，取用户名也可以放在下一次扫描所有账户的时候。
方法一：使用并查集。第一遍扫描所有账户将连通的email连通，第二遍扫描并查集hashmap时候把每个结点的所在的CEO的name取出作为key，形成map，最后再把map转成vector即可。
方法二：dfs。第一遍扫描所有账户将连通的email连通（每个账户其余email均与第一个email相连），然后，进行dfs，使用visited数组来记录结点是否访问，dfs起点是每个账户第一个email。
684. Redundant Connection
题意：检测图是不是树，给出的图多出了一条边，因此形成了环，此题给出的边的链接是小节点连接到大节点。求多余的那条边，如果有多种选项，那么最后一个多余的pair做答案。
解：此题使用并查集做，也就是说并查集也可以检测图中是否有环。对于给出的边，尝试链接到原来的图上面，先检查当前两个点在原图中是不是属于一个结点，如果是，说明两个点在未加入前已经是连通的，因此如果再加入那么必定会形成环，也就是多余的边。
如果使用dfs，那么先建图，然后检测环是不行的，因为找不到最后一个pair。一个改进的方法就是，一次加一条边到图上，然后在之前检测当前加入的边的两个顶点是不是已经连通了，已经连通的话就是答案，思路和unionfind一致。
685. Redundant Connection II
题意：与684的区别是，此题是有向图，而且有向图表面的那种环也算环。
解：此题比较难想到通用解题思路。所以从给出的例子里面找规律，看能不能总结出要求删除的边的特点。特点就是：（1）如果一个结点存在两个入度，那么两个入度中的一个必作为答案。其中具体哪个作为答案分两种情况：一种是如果去掉其中一个，剩下的图形成不了环（使用类似无向图的unionfind检测，一边加，一边检测），那么说明删除的是答案；第二种情况是，如果去掉其中一个，剩下的还是存在环，那么另一个是答案。（2）如果所有节点都是一个入度，但是存在环，此时使用类似无向图的unionfind检测解题就可以。
128. Longest Consecutive Sequence
题意：找出数组的最长大小连续(consecutive)的序列的长度，例如[100, 4, 200, 1, 3, 2]的最长大小连续的序列是[1, 2, 3, 4]，长度是4。
解：此题思想是union find，扫描数组，当我们扫描到1的时候，那么我们会先看他的邻居结点0和2是否已经在之前被扫描过，如果扫描过，那么把自己链接到原来的那一片连通的区域中，也就是说，原来一片区域的总结点数要加1。实际上，这片区域就是一个区间，我们可以使用一个技巧，也就是只使用区间左右端点来记录区间的大小，因为如果扫描的一个点落在了区间以内，那么这个点并不会使得区间的大小（也就是连续序列的长度）变化，而只可能是点落在区间左端点之前，或者右端点之后才会使得区间大小加1。
扫描数组，使用hash表记录每个元素作为所属区间边界的长度，对于元素num，先看num有没有处理过，如果没有处理过才进行处理，也就是说处理之前先查表，如果存在了，那么就直接continue。因为存在了，说明num作为边界已经处理过了，现在是必属于某个区间里面的，所以没有必要更新了。
如果num存在，那么看num-1和num+1是否存在。
如果num-1和num+1都不存在，那么num对应长度为1，存入hash表。
如果num-1存在而num+1不存在，说明num-1所在区间可以更新1，num-1所在区间本来右边界是num-1，现在更新的区间的右边界显然是num，那么在看num-1所属区间的左边界在哪，显然，hash[num-1]就是区间大小，也就是说左端点大小是num - hash[num - 1]，其在hash表中对应的值应该加1。
同理处理num-1不存在而num+1存在的情况。
当num-1和num+1都存在的时候，要把最终长度更新到两边的边界，num标记为已访问就可以了，因为我们知道，每次其实是一个一个元素的加到hash表中的，也就是说，加入num之前，num-1和num+1所在的区间的每个元素都被访问过了。
扫描过程中记录更新中可以产生的最大值，作为结果返回。
803. Bricks Falling When Hit
题意：二维矩阵表示，0表示空，1表示砖。二维矩阵第0行看作天花板。先给出这样一个矩阵，然后在给出一个二维数组坐标，表示打掉该坐标处的砖。现在要求的是每次掉落的砖，砖会掉落如果它不与天花板连通。
解：思路一：并查集。反着来添加打掉的坐标，每次当作添加砖，然后看每次有多少新砖可以连通到天花板。
具体做法是：首先，计算出初始状态的所有点的连通性：先去掉准备打掉砖的坐标，然后把剩余的砖，进行二维数组的扫描，每次考虑当前坐标和他的左边和上边的点，如果当前点和左边的点都是砖，那么进行一次union操作。两个parent合并的时候，如果有第0行的结点，那么就选其作为parent结点。
其次，倒着加入打掉的坐标，如果四个方向上有1，那么union操作，然后看新的图有多少连通点，减去之前状态的连通点就可以知道这一步连通了多少个新点，也就是会掉多少点。 其中计算连通点有一个技巧，就是把所有的顶层的点和一个额外空间进行连接，在把连通点个数记录到额外空间对应的值，这样可以一次查出所有连通点数量。
