feedingTime

bool isIncompatible(vector <string> &v1, vector <string> &v2) {
    set <string> animals;
    for (string s : v1) {
        animals.insert(s);
    }
    for (string s : v2) {
        if (animals.count(s)) {
            return true;
        }
    }
    return false;
}

bool isValidColor(vector <vector <int>> &adj, vector <int> &color, int chosenColor, int u) {
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (color[v] == chosenColor) {
            return false;
        }
    }
    return true;
}

bool isGraphColorable(vector <vector <int>> &adj, vector <int> &color, int numOfColors, int u) {
    if (u == adj.size()) return true;

    for (int i = 1; i <= numOfColors; ++i) {
        if (isValidColor(adj, color, i, u)) {
            color[u] = i;

            if (isGraphColorable(adj, color, numOfColors, u + 1)) {
                return true;
            }

            color[u] = 0;
        }
    }

    return false;
}

int feedingTime(std::vector<std::vector<std::string>> classes) {
    int n = classes.size();

    vector <vector <int>> adj(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isIncompatible(classes[i], classes[j])) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector <int> color(n);
    for (int i = 1; i <= 5; ++i) {
        if (isGraphColorable(adj, color, i, 0)) {
            return i;
        }
    }

    return -1;
}