1 对于每一个新加的点： 2  3 　　cnt++; 4  5 　　//uf做的部分就是把连起来了的岛融合在一起，调整这个cnt的 6  7 　　把自己的parent标记成自己 8  9 　　对于每一个方向：10 11 　　　　如果新的点不在范围内，或者这个点没有之前标记过（就是不存在需要融合的情况）12 　　　　　　continue13 　　　　找到这个新位置的root,如果这个newRoot和当前root不是一个，那么就说明需要融合14 15 　　　　　　roots[root] = newRoot;16 17 　　　　　　cnt--;18 　　　　　　root = newRoot.//这句不可以少，因为如果一个新加的点让cnt+1，但是它成功地连起来了多个点，就会出现多减了的情况，所以要更新root19 　　把cnt加入res中20 21 返回res

 1     static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 2      3     public List<Integer> numIslands2(int m, int n, int[][] positions) { 4         List<Integer> res = new ArrayList<Integer>(); 5         if(m <= 0 || n <= 0 || positions.length == 0 || positions[0].length == 0) { 6             return res; 7         } 8         int[] roots = new int[m * n]; 9         Arrays.fill(roots, -1);10         int cnt = 0;11         for(int[] point: positions) {12             int root = point[0] * n + point[1];13             roots[root] = root;14             cnt++;15             for(int[] dir: dirs) {16                 int newX = point[0] + dir[0];17                 int newY = point[1] + dir[1];18                 int newId = newX * n + newY;19                 if(newX < 0 || newY < 0 || newX >= m || newY >=n || roots[newId] == -1) {20                     continue;21                 }22                 int newRoot = find(roots, newId);23                 if(newRoot != root) {24                     roots[root] = newRoot;25                     root = newRoot;26                     cnt--;27                 }28             }29             res.add(cnt);30         }31         return res;32     }33     34     private int find(int[] roots, int root) {35         if(roots[root] == root) {36             return root;37         }38         return find(roots, roots[root]);39     }