# 0827. Making A Large Island
###### tags: `Leetcode` `FaceBook` `Hard` `Union Find` `Island`
Link: https://leetcode.com/problems/making-a-large-island/
## 思路
并查集先合并所有island，然后遍历所有水域，对于每一个水域上下左右如果有岛，并且father不同，那么这些岛的面积求和+1，就是现在的岛屿面积

这里要注意的是一开始合并的时候因为是用边合并，所以这种状况是考虑不到单个一个点的island的，所以

fa[i] = i
size[i] = grid[i/C][i%C]==1?1:0

保证每个节点都记录下来
其次要注意并查集的两个function
- combine function里面不要漏掉如果两个父节点相同，直接return
- find function里面最后```return fa[a] = find(fa[a])```而不是```fa[a] = find(a)```
- 然后由于原本的方法没有考虑到没有水的情况（不用合并，直接拿最大岛屿），所以加上了第30行```maxArea = Math.max(maxArea, size[i*C+j]);```
- 第40行```if(!father.contains(find(nei)))```一定不能写```if(!father.contains(nei))```debug很久才找到
## Code

class Solution {
    private int[] fa, size;
    public int largestIsland(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        fa = new int[R*C];
        size = new int[R*C];
        for(int i = 0;i < R*C;i++){
            fa[i] = i;
            size[i] = grid[i/C][i%C]==1?1:0;
        }
        for(int i = 0;i < R;i++){
            for(int j = 0;j < C;j++){
                if(grid[i][j] == 1){
                    if(j+1<C && grid[i][j+1] == 1){
                        combine(grid, i*C+j, i*C+j+1);
                    }
                    if(i+1<R && grid[i+1][j] == 1){
                        combine(grid, i*C+j, (i+1)*C+j);
                    }
                }
            }
        }
        int maxArea = 0;
        for(int i = 0;i < R;i++){
            for(int j = 0;j < C;j++){
                if(grid[i][j] == 0){
                    maxArea = Math.max(maxArea, getArea(i,j,grid));
                }
                maxArea = Math.max(maxArea, size[i*C+j]);
            }
        }
        return maxArea;
    }
    private int getArea(int x, int y, int[][] grid){
        List<Integer> neighbor = getneighbor(x,y,grid);
        Set<Integer> father = new HashSet<>();
        int area = 0;
        for(int nei:neighbor){
            if(!father.contains(find(nei))){
                father.add(find(nei));
                area+=size[find(nei)];
            }
        }
        return area+1;
    }
    private List<Integer> getneighbor(int x, int y, int[][] grid){
        int R = grid.length;
        int C = grid[0].length;
        List<Integer> ans = new ArrayList<>();
        if(x-1>=0 && grid[x-1][y]==1) ans.add((x-1)*C+y);
        if(x+1<R && grid[x+1][y]==1) ans.add((x+1)*C+y);
        if(y-1>=0 && grid[x][y-1]==1) ans.add(x*C+y-1);
        if(y+1<C && grid[x][y+1]==1) ans.add(x*C+y+1);
        return ans;
    }
    private int find(int a){
        if(fa[a] == a) return a;
        else return fa[a] = find(fa[a]);
    }
    private void combine(int[][] grid, int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(size[a]<size[b]){
            fa[a] = b;
            size[b]+=size[a];
        }
        else{
            fa[b] = a;
            size[a]+=size[b];
        }
    }
}