<p>You are given an <code>m x n</code> binary matrix <code>matrix</code>.</p>

<p>You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from <code>0</code> to <code>1</code> or vice versa).</p>

<p>Return <em>the maximum number of rows that have all values equal after some number of flips</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,1],[1,1]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> After flipping no values, 1 row has all values equal.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,1],[1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> After flipping values in the first column, both rows have equal values.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,0,0],[0,0,1],[1,1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> After flipping values in the first two columns, the last two rows have equal values.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is either&nbsp;<code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<bitset<300>> bits;
        for (int i = 0; i < m; i++) {
            bitset<300> bit;
            for (int j = 0; j < n; j++) {
                bit[j] = matrix[i][j];
            }
            bits.push_back(bit);
        }

        vector<int> ancestor(m, -1);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (ancestor[j] != -1)
                {
                    continue;
                }
                if (bits[i] == bits[j])
                {
                    ancestor[i] = j;
                    break;
                }
                else
                {
                    bool flag = true;
                    for (int k = 0; k < n; k++)
                    {
                        if (bits[i][k] != ~bits[j][k])
                        {
                            flag = false;
                            break;
                        }
                    }
                    if (flag)
                    {
                        ancestor[i] = j;
                        break;
                    }
                }
            }
        }
        int res = 0;
        unordered_map<int, int> count;
        for (int i = 0; i < m; i++)
        {
            if (ancestor[i] == -1)
            {
                ancestor[i] = i;
            }
            count[ancestor[i]]++;
            res = max(res, count[ancestor[i]]);
        }
        return res;
    }
};
68700