MultiplicationTable2.cpp

#include <vector>
#include <algorithm>
using namespace std;

class MultiplicationTable2{public:
int minimalGoodSet( vector <int> table )
{
    int n = 0;
    while (n*n < int(table.size()))
        n++;
    int ans = n;

    for (int i=0; i<n; i++)
    {
        vector<bool> S(n);
        S[i] = true;

        for (int j=0; j<n; j++)
            for (int k=0; k<n; k++)
            for (int l=0; l<n; l++)
                if (S[k] && S[l])
                    S[table[k*n+l]] = true;

        int c = 0;
        for (int i=0; i<n; i++)
            if (S[i])
                c++;
        ans = min(ans, c);
    }

    return ans;
}};