#include #include #include #include using namespace std; // union-find に値を持たせる struct UnionFind { UnionFind() {}; void unite(int, int); int find(int); bool contains(int x); int size_of(int x); int evaluate(int x); set key_set(); // parのkeySet map val; private: map par; }; int UnionFind::find(int x) { if(!contains(x)) { par[x] = -1; } return par[x] < 0 ? x : (par[x] = find(par[x])); } int UnionFind::evaluate(int x) { return val[find(x)]; } void UnionFind::unite(int x, int y) { x = find(x), y = find(y); if(x == y) { return; } if(par[x] > par[y]) { swap(x, y); } par[x] += par[y]; par[y] = x; val[x] = val[y] = val[x] + val[y]; // add } bool UnionFind::contains(int x) { return par.count(x); } set UnionFind::key_set() { set keySet; for(auto&& kv : par) { keySet.insert(kv.first); } return keySet; } int UnionFind::size_of(int x) { return -par[find(x)]; } /// vector> G; vector seen; UnionFind uf; void rec(int i) { if(seen[i]) { return; } seen[i] = true; for(int j : G[i]) { ++uf.val[j]; // 入次数をUnionFindの値として持つ rec(j); } } int main(void) { constexpr int N = 111; int n; scanf("%d", &n); G.assign(N*N, vector()); seen.assign(N*N, false); set vs; vector> memo; for(int i=0; i