Maximum Number of Consistent Truth-Tellers
Each reviewer labels every other reviewer as trustworthy, untrustworthy, or unknown. A trustworthy reviewer's labels are always correct. Find the largest set of reviewers that can all be trustworthy without contradiction.
Problem
Given an n x n matrix statements where statements[i][j] is 1 (i says j is good), 0 (i says j is bad), or 2 (no statement), and a good person always tells the truth, return the maximum number of people that can be good in a consistent assignment.
Input
An n x n matrix statements with entries in {0, 1, 2}.
Output
An integer: the maximum number of consistently-good people.
Constraints
- 1 <= n <= 15
- statements[i][j] is 0, 1, or 2; statements[i][i] == 2.
Examples
Example 1
Input
statements = [[2,1,2],[1,2,2],[2,0,2]]
Output
2
People 0 and 1 can both be good; person 2 calls 1 bad, so 2 cannot also be good.
Example 2
Input
statements = [[2,0],[0,2]]
Output
1
Each calls the other bad, so at most one is good.