# 0695. Max Area of Island
###### tags: `Leetcode` `Medium` `Union Find` `FaceBook` `BFS` `Island`
Link: https://leetcode.com/problems/max-area-of-island/
## 思路
要记得union find里面的按秩合并优化是把简单的tree往复杂的上面合并
## Code

class Solution {
    private int[] fa;
    private int[] size;
    
    public int maxAreaOfIsland(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;i++){
            for(int j = 0;j < c;j++){
                fa[i*c+j] = i*c+j;
                size[i*c+j] = grid[i][j]==0?0:1;
            }
        }
        
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                if(grid[i][j] == 1){
                    if(i+1<r && grid[i+1][j]==1){
                        combine(i*c+j, (i+1)*c+j);
                    }
                    if(j+1<c && grid[i][j+1]==1){
                        combine(i*c+j, i*c+j+1);
                    }
                }
            }
        }
        int maxArea = 0;
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                maxArea = Math.max(maxArea, size[i*c+j]);
            }
        }
        return maxArea;
    }
    
    public int find(int a){
        if(fa[a] == a) return a;
        else return fa[a] = find(fa[a]);
    }
    
    public void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(size[a]>size[b]){
            fa[b] = a;
            size[a]+=size[b];
        }
        else{
            fa[a] = b;
            size[b]+=size[a];
        }
    }
}