#include #include #include using namespace std; // N E S W constexpr array dr = {-1, 0, 1, 0}, dc = { 0, 1, 0, -1}; constexpr int dr_size = dr.size(); class UnionFind { vector par; // par[i] := iの親。iが親だったら 要素数 * -1 public: explicit UnionFind(int n) : par(n, -1) {} int root(int a); // a の親を返す。 int size(int a); // a が属するグループのサイズを返す。 void unite(int a, int b); // a と b をくっつける。 }; int UnionFind::root(int a) { if(par[a] < 0) { return a; } return par[a] = root(par[a]); } int UnionFind::size(int a) { return -par[root(a)]; } void UnionFind::unite(int a, int b) { a = root(a); b = root(b); if(a == b) { return; } if(size(a) < size(b)) { swap(a, b); } par[a] += par[b]; par[b] = a; } int R, C; void debug(const vector> &G) { for(int i=0; i> G(R, vector(C, 0)); for(int r=0; r