package advanced.datastructure.unionfind.lc305_numberofislands2;

/**
 * Created by cdai on 9/27/16.
 */
public class Solution {

    public int[] numIslands(char[][] map, int[] op) {
        int[] islands = new int[op.length];

        return islands;
    }

    private boolean union(char[][] map, int op) {
        return false;
    }

}

@@ -63,122 +63,661 @@
 2;%0A%0A
-/**%0A * Created by cdai on 9/27/16.%0A */%0Apublic class Solution %7B%0A%0A    public int%5B%5D numIslands(char%5B%5D%5B%5D map, 
+import org.junit.jupiter.api.Assertions;%0Aimport org.junit.jupiter.api.Test;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0A%0A/**%0A */%0Apublic class Solution %7B%0A%0A    @Test%0A    void test() %7B%0A        Assertions.assertEquals(Arrays.asList(1,1,1,2,2),%0A                numIslands2(3, 3, new int%5B%5D%5B%5D%7B%7B0,0%7D, %7B0,1%7D, %7B1,0%7D, %7B2,2%7D, %7B2,1%7D%7D));%0A    %7D%0A%0A    public List%3CInteger%3E numIslands2(int m, int n, int%5B%5D%5B%5D ops) %7B%0A        List%3CInteger%3E ret = new ArrayList%3C%3E();%0A        int%5B%5D%5B%5D dirs = %7B%7B1, 0%7D, %7B-1, 0%7D, %7B0, 1%7D, %7B0, -1%7D%7D;%0A        int%5B%5D islands = new int%5Bm * n%5D;%0A        Arrays.fill(islands, -1);%0A%0A        int cnt = 0;%0A        for (
 int%5B%5D op
 ) %7B%0A
@@ -712,16 +712,22 @@
 int%5B%5D op
+ : ops
 ) %7B%0A    
@@ -734,125 +734,715 @@
     
+ 
-int%5B%5D islands = new int%5Bop.length%5D;%0A%0A        return islands;%0A    %7D%0A%0A    private boolean union(char%5B%5D%5B%5D map, int op) %7B
+   int root1 = op%5B0%5D * m + op%5B1%5D;%0A            islands%5Broot1%5D = root1;%0A            cnt++;%0A            for (int%5B%5D d : dirs) %7B%0A                int x = op%5B0%5D + d%5B0%5D, y = op%5B1%5D + d%5B1%5D, id2 = x * m + y;%0A                if (x %3C 0 %7C%7C x %3E= m %7C%7C y %3C 0 %7C%7C y %3E= n %7C%7C islands%5Bid2%5D == -1) continue;%0A                int root2 = find(islands, id2);%0A                if (root1 != root2) %7B%0A                    islands%5Broot2%5D = root1; // or optimize: islands%5Broot1%5D=root2; root1=root2;%0A                    cnt--;%0A                %7D%0A            %7D%0A            ret.add(cnt);%0A        %7D%0A        return ret;%0A    %7D%0A%0A    private int find(int%5B%5D islands, int id) %7B%0A        if (islands%5Bid%5D != id) islands%5Bid%5D = find(islands, islands%5Bid%5D);
 %0A   
@@ -1457,13 +1457,19 @@
 urn 
-false
+islands%5Bid%5D
 ;%0A  

number of islands II