[LeetCode]Making A Large Island

Brute Force的做法是遍历每一个位置，看如果其变为1的话，最大的island size是多少，这一步我们dfs即可求得。假设输入矩阵m * n，那么时间复杂度为O(m^2 * n ^2)，会TLE。
事实上，每一次尝试把(i, j)处的0翻转为1，我们只需要check上下左右四个位置，如果其为1，就看其所在的island size多大。当然要注意的一点是，我们不能重复算，因为相邻的1可能属于同一个island。那么问题就变成了，如何check两个vertex所属的component是否相连？那么答案就是Union Find，在union find里我们会记录每个点对应的root，和所在的component的大小，正好符合我们的需求。优化后的union find的时间复杂度十分接近常数时间，为O(log* n)，n为union find的大小。那么对这道题来说，时间复杂度为O(m * n * log*(m * n))，代码如下：



根据union find解法的思路，我们只需要知道每一个1属于那一个island，并且对应的island多大即可。其实不需要union find，我们直接dfs来给每一个island标号即可，那么在每一次check4个邻居的时候，我们同样可以知道他们存不存在属于同一个island的元素。时间复杂度O(m * n)，代码如下：