DFS vs. Brute-Force
It is easy to misunderstand this question. A person could be good if, in the chain of all good people, no two people contradict each other.\n\n> I initially tri
It is easy to misunderstand this question. A person *could* be good if, in the chain of all good people, no two people contradict each other.\n\n> I initially tried to just check all good people agains each other (brute-force), but was not successfull. More complicated DFS solution got accepted, and later I was able to find an error and make the brute-force solution work.\n\n#### Approach 1: Brute-Force\nSame as above, we use `good` mask to check all combinations. Once you pick a set of "good" people, you check each person against each other in the set.\n\nThe tricky part is that "good" people (unless they have no answer) should not just tell "good" about each other, they also need to tell "bad" about all people who are not in the `good` set.\n\n**C++**\n```cpp\nint maximumGood(vector<vector<int>>& ss) {\n    int n = ss.size(), all = (1 << n) - 1, res = 0;\n    auto check = [&](int good) {\n        for (int i = 0; i < n; ++i)\n            if (good & (1 << i))\n                for(int j = 0; j < n; ++j)\n                    if (ss[i][j] != 2 && ss[i][j] != (good & (1 << j) ? 1 : 0))\n                        return false;\n        return true;\n    };\n    for (int good = 1; good <= all; ++good) {\n        int cnt = bitset<16>(good).count();\n        if (cnt > res && check(good))\n            res = cnt;\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(2 ^ n * n * n). \n- Memory: O(1).\n\n#### Approach 2: DFS\nThis is more complicated, and the benefit is that we can identify definitelly "bad" people upfront (by finding a controversy), and exclude them from the search.\n\nFor each person, we assume that this person is "good", and run DFS to find all "bad" people for that assumption. As we do DFS, we visit all allegedly "good" people. If the list of bad people intersect with the list of good people - this person cannot be good. \n\nAfter we collect this information, we try all combinations of people; for each combination we get the collective list of \u201Cbad\u201D people. If this list does not include anyone in our combination, this combination of good people is valid.\n\n**C++**\n```cpp\nint dfs(vector<vector<int>>& ss, int i, int &good) {\n    int bad = 0;\n    if ((good & (1 << i)) == 0) {\n        good |= 1 << i;\n        for (int j = 0; j < ss.size(); ++j) {\n            if (ss[i][j] == 0)\n                bad |= 1 << j;\n            else if (ss[i][j] == 1)\n                bad |= dfs(ss, j, good);\n        }\n    }\n    return good & bad ? INT_MAX : bad;\n}\nint maximumGood(vector<vector<int>>& ss) {\n    int n = ss.size(), all = (1 << n) - 1, res = 0, bad_masks[16] = {}, good_masks[16] = {}, bad_mask = 0;\n    for (int i = 0; i < n; ++i) {\n        int good = 0;\n        bad_masks[i] = dfs(ss, i, good);\n        good_masks[i] = good;\n        if (bad_masks[i] == INT_MAX)\n            bad_mask |= (1 << i);\n    }\n    for (int can_be_good = 1; can_be_good <= all; ++can_be_good) {\n        if (can_be_good & bad_mask)\n            continue;\n        int bad = 0, good = 0;\n        if (__builtin_popcount(can_be_good) > res) {\n            for (int i = 0; i < n; ++i)\n                if (can_be_good & (1 << i)) {\n                    bad |= bad_masks[i];\n                    good |= good_masks[i];\n                }\n            if ((good & bad) == 0)\n                res = __builtin_popcount(good);\n        }\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(2 ^ n * n). \n- Memory: O(n) for the recursion and to store masks.
[]