SRM685 Div1 Easy "MultiplicationTable2"
解法
サブセットTにindex iを使うぞ! と決めると、goodなTを作るために必要な他のindexを芋づる式に導き出すことができる。
なので、index 0~n-1を順に試して、必要なindexが一番少ないものを答えとすればよい。
事後
SRM696から過去へ遡ってEasyやってきたけど、久しぶりにEasyらしい問題ですね(白目)
ソースコード
vector<int> t; int n; bool use[55]; class MultiplicationTable2 { public: int minimalGoodSet(vector<int> table) { t = table; n = (int) sqrt(table.size()); int ans = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { use[j] = false; } dfs(i); int count = 0; for (int j = 0; j < n; j++) { if (use[j]) count++; } ans = min(ans, count); } return ans; } void dfs(int cur) { use[cur] = true; for (int i = 0; i < n; i++) { if (!use[i]) continue; for (int j = 0; j < n; j++) { if (!use[j]) continue; int id = i * n + j; if (use[t[id]]) continue; dfs(t[id]); } } } };