class DSU { private: vector parent; vector rank; public: DSU(int n) { parent.resize(n); rank.resize(n, 0); for (int i = 0; i < n; ++i) { parent[i] = i; } } void init(){ for (int i = 0; i < parent.size(); ++i) { parent[i] = i; } } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { parent[x] = y; } else { parent[y] = x; if (rank[x] == rank[y]) { rank[x]++; } } } bool isConnected(int x, int y) { return find(x) == find(y); } };