[LeetCode]Bricks Falling When Hit

图的连接性的问题，很自然地会想到用并查集。这道题的问题是我们每次erase一个1，是相当于disconnect两个node，但是并查集只支持连接两个node，而不支持disconnect，所以这里我们要想办法把disconnect变成connect。如果我们按照从头到尾的顺序disconnect的话，我们反向connect就可以达到一样的效果。具体的做法是，把所有对于要抹去的brick先从grid当中消除，之后我们反向加入brick，然后看每次并查集中对应的component的size有没有变化。由于所有在顶端的点都是自动联通的，我们设定一个super node链接所有顶端的节点。假设grid有r行c列，hits长度为n，时间复杂度O((r * c + n) * lg*(r * c))，代码如下：