#include #include using namespace atcoder; using namespace std; using ll = int; using ld = long double; struct unionfind { vectorpar,siz; unionfind(ll n): par(n,-1),siz(n,1){} ll root(ll x){ if (par[x]==-1) { return x; }else{ return par[x]=root(par[x]); } } bool issame(ll x,ll y){ return root(x)==root(y); } bool unite(ll x,ll y){ x=root(x); y=root(y); if (x==y) { return false; } if (siz[x]> h >> w; vector>a(h,vector(w)); for (ll i = 0; i < h; i++) { for (ll j = 0; j < w; j++) { cin >> a[i][j]; } } unionfind uf(h*w); for (ll i = 0; i < h; i++) { for (ll j = 0; j < w; j++) { if (i!=0) { if (a[i-1][j]&&a[i][j]) { uf.unite((i-1)*w+j,i*w+j); } } if (j!=0) { if (a[i][j-1]&&a[i][j]) { uf.unite(i*w+j-1,i*w+j); } } } } vectormemo(h*w,0); ll ans=0; for (ll i = 0; i < h; i++) { for (ll j = 0; j < w; j++) { if (a[i][j]==0) { continue; } if (memo[uf.root(i*w+j)]==0) { ans++; } memo[uf.root(i*w+j)]++; } } cout << ans << endl; }