#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; const ll MOD = 1000000007; #define rep(i,n) for(int i=0;i=0;i--) #define all(x) (x).begin(),(x).end() int H, W; class UnionFind { //par[i]:ノードiの親 //count[i]:iが親の時、iが属するグループのノード数 vector par; int m_groupCount = 0; public: UnionFind(int N) { par.push_back(0); m_groupCount = N; for (int i = 1; i <= N; i++) { //最初は全てが根であるとして初期化 par.push_back(i); } } //データxが属する木の根を再帰で得る:root(x) = {xの木の根} int root(int x) { if (par[x] == x) return x; //ついでに親を張り替え return par[x] = root(par[x]); } //xとyの木を併合 void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける par[rx] = ry; //木の併合によってグループが1つ減る m_groupCount--; } // 2つのデータx, yが属する木が同じならtrueを返す bool same(int x, int y) { return root(x) == root(y); } //UnionFindのグループの個数を返す int groupCount() { return m_groupCount; } }; bool IsInRange(int w, int h) { return 0 <= w && w <= W - 1 && 0 <= h && h <= H - 1; } int ToIndex(int w, int h) { return h * W + w; } int main() { cin >> H >> W; UnionFind uf(H * W); set s; rep(h, H) { rep(w, W) { int a; cin >> a; if (a != 1) continue; int idx = ToIndex(w, h); //1の場合setで保存 s.insert(idx); //上と左だけ結合判定 if (IsInRange(w - 1, h)) { int i = ToIndex(w - 1, h); if (s.count(i) > 0) uf.unite(idx, i); } if (IsInRange(w, h - 1)) { int i = ToIndex(w, h - 1); if (s.count(i) > 0) uf.unite(idx, i); } } } //個数確認 //親の個数をカウント ll count = 0; for (auto x : s) { if (uf.root(x) == x) count++; } cout << count << endl; return 0; }