WARush

SRMの結果とか、解けた問題のコードを書いていきます

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]);
            }
        }
    }
};