import std.experimental.all; T read(T)() { return readln.chomp.to!T; } T[] reads(T)() { return readln.split.to!(T[]); } alias readint = read!int; alias readints = reads!int; // 3.3 sec で AC int calc(int[][] g) { int rows = cast(int)g.length; int cols = cast(int)g[0].length; auto delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]; void fill(int row, int col, int[][] g, int[][] used) { assert(g[row][col] == 1); auto q = DList!(int)(); // [row, col] で配列生成すると TLE (2 sec 近く遅くなる) q.insertBack((row << 16) | col); while (!q.empty) { auto a = q.front; q.removeFront(); int r = (a >> 16), c = a & 0xffff; if (used[r][c]++) continue; foreach (d; delta) { int r2 = r + d[0]; int c2 = c + d[1]; if (!(0 <= r2 && r2 < rows && 0 <= c2 && c2 < cols)) continue; if (g[r2][c2] == 0 || used[r2][c2]) continue; q.insertBack((r2 << 16) | c2); } } } int ans = 0; auto used = new int[][](rows, cols); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (used[i][j]) continue; if (g[i][j] == 1) { ans++; fill(i, j, g, used); } } } return ans; } int calc2(int[][] g) { int rows = cast(int)g.length; int cols = cast(int)g[0].length; int toIndex(int r, int c) { return r * cols + c; } auto uf = new UnionFind(rows * cols); int one = 0; int uniteCount = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (g[i][j] == 0) continue; one++; if (i > 0 && g[i-1][j] == 1) { int a = toIndex(i, j); int b = toIndex(i-1, j); if (uf.unite(a, b)) uniteCount++; } if (j > 0 && g[i][j-1] == 1) { int a = toIndex(i, j); int b = toIndex(i, j-1); if (uf.unite(a, b)) uniteCount++; } } } return one - uniteCount; } void main() { auto hw = readints; int h = hw[0], w = hw[1]; auto g = new int[][](h, w); for (int i = 0; i < h; i++) { g[i][] = readints; } // writeln(calc(g));// AC 3.2 sec writeln(calc2(g)); } class UnionFind { private int[] _data; this(int n) { _data = new int[](n + 1); _data[] = -1; } int root(int a) { if (_data[a] < 0) return a; return _data[a] = root(_data[a]); } bool unite(int a, int b) { /* int ra = root(a); int rb = root(b); if (ra == rb) return false; // ra に rb を繋げる _data[ra] += _data[rb]; _data[rb] = ra; return true; */ int ra = root(a); int rb = root(b); if (ra != rb) { if (_data[rb] < _data[ra]) swap(ra, rb); _data[ra] += _data[rb]; _data[rb] = ra; } return ra != rb; } bool isSame(int a, int b) { return root(a) == root(b); } /// a が属する集合のサイズ int groupSize(int a) { return -_data[root(a)]; } }